Starry Sky Tree
概要
- 長さ \(n\) の数列: \(v = \{ v_0, v_1, \ldots, v_{n-1} \} = \{0,0,\ldots,0\}\)
- 次の2つの操作が許される
add(l, r, x)
: \(v_i \leftarrow v_i + x\) for each \(l \leq i \leq r\)
max(l, r)
: \(\max \{ x_i : l \leq i \leq r \}\) を返す
template<typename T=int>
struct SS {
int N;
T*ar_inc, *ar;
SS(int n) {
N = n;
ar = new T[N*2];
ar_inc = new T[N*2];
}
~SS() {
delete[] ar;
delete[] ar_inc;
}
void add_sub(int l, int r, T x, int idx, int ll, int rr) {
if (r <= ll or rr <= l) return;
if (ll < l or r < rr) {
add_sub(l, r, x, idx*2+1, ll, (ll+rr)/2);
add_sub(l, r, x, idx*2+2, (ll+rr)/2, rr);
} else {
ar_inc[idx] += x;
while (idx) {
idx = (idx-1) / 2;
int c1 = idx * 2 + 1,
c2 = idx * 2 + 2;
ar[idx] = std::max<T>(ar[c1]+ar_inc[c1], ar[c2]+ar_inc[c2]);
}
}
}
void add(int l, int r, T x) {
add_sub(l, r, x, 0, 0, N);
}
T max_sub(int l, int r, int idx, int ll, int rr) {
if (rr <= l or r <= ll) return -inf;
if (l <= ll and rr <= r) return ar[idx] + ar_inc[idx];
T left = max_sub(l, r, idx*2+1, ll, (ll+rr)/2);
T right = max_sub(l, r, idx*2+2, (ll+rr)/2, rr);
return std::max<T>(left, right) + ar_inc[idx];
}
T max(int l, int r) { return max_sub(l, r, 0, 0, N); }
};
Example
SS<>sky(4);
sky.add(0, 4, 1); // [1, 1, 1, 1]
assert(sky.max(0, 4) == 1);
assert(sky.max(1, 4) == 1);
assert(sky.max(0, 3) == 1);
sky.add(2, 4, -1); // [1, 1, 0, 0]
assert(sky.max(0, 1) == 1); // max of [1]
assert(sky.max(0, 3) == 1); // max of [1, 1, 0]
assert(sky.max(2, 3) == 0); // [0]
assert(sky.max(2, 4) == 0); // [0, 0]