SimpleSeg
alias SimpleSeg(T, alias opTT, T eT, alias Engine = SimpleSegEngine) = SegTree!(Engine, T, binaryFun!opTT, eT)
1 import std.algorithm : max;
2 ///int型でmax(...)が計算できる、つまりRMQ
3 auto seg = SimpleSeg!(int, (a, b) => max(a, b), 0)(3);
4
5 //[2, 1, 4]
6 seg[0] = 2; seg[1] = 1; seg[2] = 4;
7 assert(seg[0..3].sum == 4); //max(2, 1, 4) == 4
8
9 //[2, 1, 5]
10 seg[2] = 5;
11 assert(seg[0..2].sum == 2); //max(2, 1) == 2
12 assert(seg[0..3].sum == 5); //max(2, 1, 5) == 5
13
14 //[2, 11, 5]
15 seg[1] = seg[1] + 10;
16 assert(seg[0..3].sum == 11);
SegTree
T型の配列aについて、opTT(al..r)が高速に計算できる。 opTTは結合率を満たす2引数関数, eTは単位元。