应用场景：

单点更新以及区间求和问题，比如已知一个数列长度为n，你需要进行w次修改一个值和q次查询一个区间内的和。

修改和查询的复杂度都是O(logN)。

原理：

黑色（A）的是原数组，我们要增加一些节点用来记录一个区间的信息；这些红色节点（C）形成了层状结构，越上层的节点覆盖的区间范围越大。首先标号为i的红色节点位于第几层，是由其二进制表示的末位有几个0决定的：比如任何奇数都在第0层，而2(10)、6(110)在第1层，8(1000)在第3层。

C[1]=A[1]   C[2]=C[1]+A[2]  C[4]=C[2]+C[3]+A[4]  C[6]=C[5]+A[6]  C[8]=C[4]+C[6]+C[7]+A[8]

我们发现，第0层的C等于A，第1层的由1个C与1个A相加，……，第3层的由3个C与1个A相加。其中位于第k层的C[i]对应的A就是A[i]，而对应的C节点是：C[i-1],C[i-2],C[i-4]...C[i-2^(K-1)]

求和：如果我们要求区间i~j的和，我们利用1~j的和减去1~i的和。其中假设i=11，二进制表示为1011，则从1000开始，“逐位恢复1”: 1000，1010，1011，则SUM[11]=C[8]+C[10]+C[11], 同理，9: 1000,1001  SUM[9]=C[8]+C[9]。 这个逐位恢复1的过程，也可以解释为，若i的二进制表示最低位1为k位，则SUM[i]=C[i]+C[i-2^k]+C[i-2^{k+1}]……直到索引恰好为2幂次。这样做的好处是每一轮减去的数可以通过(i)&(-i)求得。比如i=6, 0000 0110 & 1111 1010 = 0000 0010，即6-2=4。当索引恰好为2幂次时，i&(-i)==i， 这一轮减去后，恰好为0。

假设数组长度为n,则数的二进制表示有logn位，每次求和需要访问2logn次，则查询的复杂度是logn。

修改：如果我们要更新第i个位置的数，i的二进制表示中末位有k个0，则我们需要更新C[i], C[i+2^k]，C[i+2^k+2^(k+1)]……直到索引大于n。这里每一轮加上的数也可以通过(i)&(-i)求得， 则每次修改的复杂度也是logn。 

例题1：https://www.luogu.com.cn/problem/P3368

此题目中，我们用C记录的是这个区间中累加的数值，其更新类似经典树状数组的求和，比如3~6区间加2，我们就先在表示1~6区间的C[4],C[6]节点上加2，再在表示1~2区间的C[2]节点上减2。此时，如果查询1的值，依次经过C[1]=0,C[2]=-2,C[4]=2,C[8]=0,得到1的值变化了0；如果查询5的值，依次经过C[5]=0,C[6]=2,C[8]=0,得到5的值变化了2。

int lowbit(int x){return x&(-x);}void update(int x, int y, int k, int N, vector<int>&C){if(x==0){int tmp = y;while(tmp>0){C[tmp] += k;tmp -= lowbit(tmp);}}else{update(0,y,k,N,C);update(0,x,-k,N,C);}
}int cal(int x, int N, vector<int>& C){int tmp = 0;while(x<=N){tmp += C[x];x += lowbit(x);}return tmp;
}int main()
{int N,M;cin>>N>>M;vector<int> A(N+1);vector<int> C(N+1,0); //record the changed value of the intervalfor(int i=1;i<=N;i++) cin>>A[i]; //note the index begins with 1int op,x,y,k;for(int i=0;i<M;i++){cin>>op;if(op==1){cin>>x>>y>>k;update(x,y,k,N,C);}else{cin>>x;cout<<A[x]+cal(x,N,C)<<'\n';}}return 0;
}

例题2：LeetCode 315

解决这个问题我们首先要进行离散化。也就是对于数组中的一个值v，我们不记录v，而是记录它是数组中第k大的元素。之后，我们用桶来记录数量。序列[5,2,6,6,1] 就被转化成了[1,1,1,2]。

我们从一个全0数组开始，从右边遍历数组，单点更新桶数组，最后输出C就可以了。

排序、桶化需要nlogn，每次更新数组需要logn，共更新n次，则算法复杂度为nlogn。

class Solution {
public:static bool cmp(const vector<int>& x, const vector<int>& y){return x[0]<y[0];}static bool cmp2(const vector<int>& x, const vector<int>& y){return x[1]<y[1];}int lowbit(int x){return x&(-x);}int sum(int x, vector<int>& c){int tmp = 0;while(x>0){tmp += c[x];x -= lowbit(x);}return tmp;}void update(int x, int j, vector<int>& c){while(x<=j){c[x] += 1;x += lowbit(x);}}vector<int> countSmaller(vector<int>& nums) {int m = nums.size();if(m<=1) return vector<int>(m,0);vector<vector<int>> n;for(int i=0;i<m;i++){vector<int> tmp{nums[i],i,0};n.push_back(tmp);}//n[i][0]=v, n[i][1]=k, n[i][2]=j means: //value v on the k-th position of nums is the j-th larger number sort(n.begin(),n.end(),cmp);int last = n[0][0];int j = 1;n[0][2] = 1;for(int i=1;i<m;i++){if(n[i][0]!=last){j ++;n[i][2] = j;last = n[i][0];}else n[i][2] = j;}sort(n.begin(),n.end(),cmp2);vector<int> C(j+1,0);vector<int> ans(m,0);int id;for(int i=m-1;i>=0;i--){id = n[i][2];ans[i] = sum(id-1,C);update(id,j,C);}return ans;}
};

参考：

1】https://www.cnblogs.com/xenny/p/9739600.html

2】https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/solution/ji-suan-you-ce-xiao-yu-dang-qian-yuan-su-de-ge-s-7/