본문 바로가기
라이브러리/자료구조

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
BIT  (0) 2021.03.22
DSU  (0) 2021.03.22
Tree  (0) 2020.08.06

댓글0