세그먼트 트리 템플릿 (c++)

재귀 + 1-based (수정 용이)

class segtree {
public:
  int size;
  vector<int> tree;
  segtree(int n) {
    for (size = 1; size < n; size <<= 1)
      ;
    tree.resize(size * 2);
  }
  void update(int pos, int val) {
    pos += size - 1;
    tree[pos] += val;
    for (pos /= 2; pos; pos /= 2) {
      tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
    }
  }
  int query(int n, int s, int e, int l, int r) {
    if (r < s || e < l)
      return 0;
    if (l <= s && e <= r)
      return tree[n];
    int m = (s + e) >> 1;
    return query(n * 2, s, m, l, r) + query(n * 2 + 1, m + 1, e, l, r);
  }
  int query(int l, int r) { return query(1, 1, size, l, r); }
};

 

 

비재귀 + 0-based (빠름)

class segtree {
public:
  int size;
  vector<ll> tree;
  segtree(int n) {
    size = 1;
    while (size < n)
      size *= 2;
    tree.assign(2 * size, 0);
  }

  void update(int i, ll x) {
    i += size;
    tree[i] += x;
    for (i /= 2; i >= 1; i /= 2) {
      tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
  }

  // [l, r)
  ll query(int l, int r) {
    ll res = 0;
    for (l += size, r += size; l < r; l /= 2, r /= 2) {
      if (l % 2)
        res = res + tree[l++];
      if (r % 2)
        res = res + tree[--r];
    }
    return res;
  }
};