본문 바로가기
알고리즘/라이브러리

BIT

by 유시은 2021. 3. 22.
struct Bit {
  ll cap;
  vector<ll> arr, tree;

  Bit(int size) {
    cap = size + 1;
    arr.resize(cap, 0);
    tree.resize(cap, 0);
  }

  void update(int i, ll x) {
    ll diff = x;
    arr[i] += x;
    while (i < cap) {
      tree[i] += diff;
      i += i & -i;
    }
  }
  ll query(int l, int r) const {
    return pquery(r) - pquery(l - 1);
  }
  ll pquery(int i) const {
    ll ret = 0;
    while (i > 0) {
      ret += tree[i];
      i -= i & -i;
    }
    return ret;
  }
};

 

'알고리즘 > 라이브러리' 카테고리의 다른 글

Segment tree  (0) 2021.08.12
DSU  (0) 2021.03.22
Rabin karp  (0) 2021.02.10
BFS  (0) 2020.12.13
Suffix Array와 LCP Array  (0) 2020.09.23

댓글