セグメント木(区間加算,区間最大,単独書換)[deprecated]

keyword:

カートに追加

overview

次のクエリを処理できる. - 1つの要素を書き換える. - 区間の要素すべてに加算する. - 区間の要素の最大値を計算する. 0-indexedで,[begin,end).beginを含み,endを含まない. 何度も加減算を繰り返すと内部でオーバーフローを起こす可能性. インデックスは size_t ではなく int で扱う. コピーを繰り返すため,T に指定する型はプリミティブ型か小さな構造体だと嬉しい

usage

SegmentTree(int n)
; [0,n) の配列を確保する.
T SegmentTree::get_val(int idx)
; idx の要素の値を取得する.
void SegmentTree::set_val(int idx, T e)
; idx の要素の値をeに書き換える.
void SegmentTree::add_valrange(int begin, int end, T e)
; 区間[begin,end)にeを加算する
void SegmentTree::get_maxrange(int idx, T e)
; 区間[begin,end)の最大値を計算する
void SegmentTree::get_maxrangeIdx(int idx, T e)
; 区間[begin,end)の最大値が存在する要素のインデックスを取得する

verified

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208410#1 (setval, getminrange)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208412#1 (addvalrange, getval)
https://yukicoder.me/submissions/294581 (addvalrange, getminrange)
Legacy: 
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2521389#1 (setval, getminrange)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2521434#1 (addvalrange, getval)
https://yukicoder.me/submissions/227863 (addvalrange, getminrange)

references

プログラミングコンテストチャレンジブック
https://www.slideshare.net/kazumamikami1/ss-15160153

code