dkh.datastructure.segtree
-
Declaration
template SimpleSeg(T, alias opTT, T eT, alias Engine = SimpleSegEngine)SegTree
Discussion
T型の配列aについて、opTT(a[l..r])が高速に計算できる。 opTTは結合率を満たす2引数関数, eTは単位元。
Examples
import std.algorithm : max; ///int型でmax(...)が計算できる、つまりRMQ auto seg = SimpleSeg!(int, (a, b) => max(a, b), 0)(3); //[2, 1, 4] seg[0] = 2; seg[1] = 1; seg[2] = 4; assert(seg[0..3].sum == 4); //max(2, 1, 4) == 4 //[2, 1, 5] seg[2] = 5; assert(seg[0..2].sum == 2); //max(2, 1) == 2 assert(seg[0..3].sum == 5); //max(2, 1, 5) == 5 //[2, 11, 5] seg[1] = seg[1] + 10; assert(seg[0..3].sum == 11);
-
Declaration
template LazySeg(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL, alias Engine = LazySegEngine)遅延伝搬SegTree
Discussion
T型の配列aに対して、a[l..r] += x(xはL型)、opTT(a[l..r])が高速に計算できる
Parameters
opTT(T, T)の演算(結果をまとめる)
opTL(T, L)の演算(クエリを適用する)
opLL(L, L)の演算(クエリをまとめる)
eTTの単位元
eLLの単位元
Examples
import std.algorithm : max; ///区間max, 区間加算 auto seg = LazySeg!(int, int, (a, b) => max(a, b), (a, b) => a+b, (a, b) => a+b, 0, 0)([2, 1, 4]); //[2, 1, 4] seg[0] = 2; seg[1] = 1; seg[2] = 4; assert(seg[0..3].sum == 4); //[2, 1, 5] seg[2] = 5; assert(seg[0..2].sum == 2); assert(seg[0..3].sum == 5); //[12, 11, 5] seg[0..2] += 10; assert(seg[0..3].sum == 12);