ツリー配列(Binary Indexed Tree(BIT)

1319 ワード

他のことはともかく、このブログは私の学習のためのツリー配列に大きな助けを与えてくれました。
http://blog.csdn.net/int64ago/article/details/7429868
いくつかのよく使う操作を言います。
1 inline int lowbit(int x)
2 {
3     return x&(-x);
4 }
 1 int read(int x)
 2 {
 3     int sum=0;
 4     while(x)
 5     {
 6         sum+=bit[x];
 7         x-=lowbit(x);
 8     }
 9     return sum;
10 }
1 void add(int x,int num)
2 {
3     while(x<=n)
4     {
5         bit[x]+=num;
6         x+=lowbit(x);
7     }
8 }