Range Sum Query

動的セグメント木(Dynamic Segment Tree)

概要

セグメント木の動的バージョン

大きい区間(区間\([0, 10^9)\)等)を扱えたり、メモリ量少なめに区間クエリを処理することができる。

計算量

扱う区間のサイズをNとする。(つまり、区間\([0, N)\)を扱う動的セグメント木)

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

  • 区間和: \(O(\log N)\)

実装

#define MOD 1000000007

struct Node {
  Node *left, *right;
  ll v;

  Node() : left(nullptr), right(nullptr), v(0) {}
};

// Dynamic Segment Tree
class SegmentTree {
  Node *root;
  int n, n0;

  ll query(int a, int b, Node *n, int l, int r) {
    if(a <= l && r <= b) {
      return n->v;
    }
    if(r <= a || b <= l) {
      return 0;
    }

    ll lv = n->left ? query(a, b, n->left, l, (l + r) >> 1) : 0;
    ll rv = n->right ? query(a, b, n->right, (l + r) >> 1, r) : 0;
    return (lv + rv) % MOD;
  }

public:
  SegmentTree(int n) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;
    root = new Node();
  }
  ~SegmentTree() {
    delete root; root = nullptr;
  }

  void update(int k, ll x) {
    Node *n = root;
    int l = 0, r = n0;
    n->v = (n->v + x) % MOD;
    while(r-l > 1) {
      int m = (l + r) >> 1;
      if(k < m) {
        if(!n->left) n->left = new Node();
        n = n->left;

        r = m;
      } else {
        if(!n->right) n->right = new Node();
        n = n->right;

        l = m;
      }
      n->v = (n->v + x) % MOD;
    }
  }

  ll query(int a, int b) {
    return query(a, b, root, 0, n0);
  }

  ll lquery(int b) {
    return query(0, b, root, 0, n0);
  }

  ll rquery(int a) {
    return query(a, n0, root, 0, n0);
  }
};

Verified

  • AtCoder: "AtCoder Regular Contest 054 - D問題: バブルソート": source (C++14, 650ms)