セグメント木

keyword:

カートに追加

overview

次のクエリを処理できる.時間計算量O(log_2(N)) - 1つの要素を書き換える - 1つの要素に加算する - 1つの要素の値を求める - 区間の要素すべてを1つの値で埋める - 区間の要素すべてに加算する - 区間の要素の和を求める - 区間の要素の最大値を計算する 0-indexedで,[begin,end).beginを含み,endを含まない. 空間計算量はO(4NX+NC).X は sizeof(T),C は sizeof(struct{int;bool;}). 何度も加減算を繰り返すと内部でオーバーフローを起こす可能性. インデックスは size_t ではなく int で扱う.

verified

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208770#1
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208769#1
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208768#1
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208771#1
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208772#1
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208773#1
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3208777#1

references

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

code