セグメント木(単独書き換え,区間演算)

keyword:

カートに追加

overview

次のクエリを処理できる. - 1つの要素を書き換える. - 区間の要素全てにfunc_を適応した値を求める. 十分な高速化が施されている.と思われる.

usage

; 非負整数,区間最大値の場合.
SegmentTreeQ s(10, [](int x, int y) {return max(x, y); }, 0);

verified

https://beta.atcoder.jp/contests/dwacon2018-final-open/submissions/2050384

references

http://d.hatena.ne.jp/komiyam/20131202/1385992406
http://proc-cpuinfo.fixstars.com/2017/07/optimize-segment-tree/
https://beta.atcoder.jp/contests/dwacon2018-final-open/submissions/2049865

code