티스토리 뷰

struct FenwickTree {

   vector<inttree;

   FenwickTree(int n) : tree(n + 1) {}

   inline int sum(int pos) {

       ++pos;

       int ret = 0;

       while (pos > 0) {

          ret += tree[pos];

          pos &= (pos - 1);

       }

       return ret;

   }

   inline void add(int posint val) {

       ++pos;

       while (pos < (inttree.size()) {

          tree[pos] += val;

          pos += (pos & -pos);

       }

   }

};



사용법

생성자 FenwickTree fenwickTree(n) : n은 들어갈 노드의 개수

int sum(int pos) : 0번~pos번째까지의 합을 구해준다.(내부적으로 1~pos+1로 동작)

void add(int pos, int val) : pos번째 노드에 val을 더해준다.


성능

합이랑 더하기 시간복잡도 모두 O(lgN)


응용

5~8번 노드의 구간합은 fenwickTree.sum(8) - fenwickTree.sum(5-1)

댓글
댓글쓰기 폼
공지사항
Total
317,763
Today
27
Yesterday
84
링크
«   2018/08   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
글 보관함