LazySeg
alias LazySeg(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL, alias Engine = LazySegEngine) = SegTree!(Engine, T, L, binaryFun!opTT, binaryFun!opTL, binaryFun!opLL, eT, eL)
- opTT
- opTL
- opLL
- eT
- eL
1 import std.algorithm : max;
2 ///区間max, 区間加算
3 auto seg = LazySeg!(int, int,
4 (a, b) => max(a, b), (a, b) => a+b, (a, b) => a+b, 0, 0)([2, 1, 4]);
5
6 //[2, 1, 4]
7 seg[0] = 2; seg[1] = 1; seg[2] = 4;
8 assert(seg[0..3].sum == 4);
9
10 //[2, 1, 5]
11 seg[2] = 5;
12 assert(seg[0..2].sum == 2);
13 assert(seg[0..3].sum == 5);
14
15 //[12, 11, 5]
16 seg[0..2] += 10;
17 assert(seg[0..3].sum == 12);
遅延伝搬SegTree
T型の配列aに対して、al..r += x(xはL型)、opTT(al..r)が高速に計算できる