Starry Sky Tree

概要

  • 長さ \(n\) の数列: \(v = \{ v_0, v_1, \ldots, v_{n-1} \} = \{0,0,\ldots,0\}\)
  • 次の2つの操作が許される
    1. add(l, r, x): \(v_i \leftarrow v_i + x\) for each \(l \leq i \leq r\)
    2. max(l, r): \(\max \{ x_i : l \leq i \leq r \}\) を返す

seq.starry.cc

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]