Range Minimum Query and Range Sum Query (RMQ and RSQ)

概要

以下のクエリが処理できる遅延評価セグメント木の実装

  • \(a_l, a_{l+1}, ..., a_{r-1}\) の値を \(x\) に更新

  • \(a_l, a_{l+1}, ..., a_{r-1}\) の総和を求める

計算量

  • 区間更新: \(O(\log N)\)

  • 総和計算: \(O(\log N)\)

実装

高速化のために非再帰で実装。

#include<algorithm>
using namespace std;
using ll = long long;

#define LV 20

class SegmentTree {
  const static ll inf = (1LL << 60) - 1;

  int n0, n;
  ll *data, *lazy;
  int ids[2*LV], cur = 0;

  void update_ids(int l, int r) {
    int l0 = (l + n0), r0 = (r + n0);
    int lb = (l0 & -l0) >> 1, rb = (r0 & -r0) >> 1;
    l0 >>= 1; r0 >>= 1;
    cur = 0;
    while(l0 > 0 && l0 < r0) {
      if(!rb) ids[cur++] = r0;
      if(!lb) ids[cur++] = l0;
      lb >>= 1; rb >>= 1;
      l0 >>= 1; r0 >>= 1;
    }
    while(l0 > 0) {
      ids[cur++] = l0;
      l0 >>= 1;
    }
  }

  void propagates() {
    for(int i=cur-1; i>=0; --i) {
      int k = ids[i];

      ll v = lazy[k-1];
      if(v == 0) continue;

      lazy[2*k-1] += v; data[2*k-1] += v;
      lazy[2*k] += v; data[2*k] += v;
      lazy[k-1] = 0;
    }
  }

public:

  SegmentTree(int n) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;
    data = new ll[2*n0];
    lazy = new ll[2*n0];
    for(int i=0; i<2*n0; ++i) data[i] = 0, lazy[i] = 0;
  }

  void update(int l, int r, ll x) {
    update_ids(l, r);
    propagates();

    int l0 = l + n0, r0 = r + n0;
    while(l0 < r0) {
      if(r0 & 1) {
        --r0;
        lazy[r0-1] += x; data[r0-1] += x;
      }
      if(l0 & 1) {
        lazy[l0-1] += x; data[l0-1] += x;
        ++l0;
      }
      l0 >>= 1; r0 >>= 1;
    }

    for(int i=0; i<cur; ++i) {
      int k = ids[i];
      data[k-1] = max(data[2*k-1], data[2*k]);
    }

  }

  ll query(int l, int r) {
    update_ids(l, r);
    propagates();

    int l0 = l + n0, r0 = r + n0;

    ll s = -inf;
    while(l0 < r0) {
      if(r0 & 1) {
        --r0;
        s = max(s, data[r0-1]);
      }
      if(l0 & 1) {
        s = max(s, data[l0-1]);
        ++l0;
      }
      l0 >>= 1; r0 >>= 1;
    }
    return s;
  }
};

Verified

  • AtCoder: "Educational DP Contest / DP まとめコンテスト - W問題: Intervals": source (C++14, 301ms)

  • AtCoder: "AtCoder Regular Contest 056 - D問題: サケノミ": source (C++14, 983ms)