首页 > 代码库 > 树状数组

树状数组

 1 //一、 树状数组(BT)的第 i 位存储的是以 i 为结尾的长度为lowbit(i) 的一段的和
 2 int lowBit(x) {
 3     return x & -x;
 4 }//lowBit 补码(正数变负数,先减去1之后按位取反(0→1,1→0)eg:-1=-(1)=-(0001-1)=-(0000)=1111) 
 5 int lowBit(x) {
 6     return x & -x;
 7 }
 8 const int maxn = 100003;
 9 int n, bt[maxn];
10 void btAdd(int pos, int delta) {
11     for (; pos <= n; pos += lowBit(pos)) {
12         bt[pos] += delta;
13     }
14 }
15 int btSum(int pos) {
16     int ans = 0;
17     for (; pos; pos -= lowBit(pos)) {
18         ans += bt[pos];
19     }
20     return ans;
21 }
22 int main() {
23 }

 

树状数组