樹狀數組能夠完成如下操作：

給一個序列a0-an

計算前i項和

對某個值加x

時間o(logn)

?

注意：有人覺得前綴和就行了，但是你還要維護啊，改變某個值，一個一個改變前綴和就是o(n)了。

線段樹樹狀數組的題就是這樣，維護一個樹，比較容易看出來。

?

?

線段樹：

https://blog.csdn.net/hebtu666/article/details/82691008

如果使用線段樹，只需要對網址中的實現稍微修改即可。以前維護最小值，現在維護和而已。

注意：要求只是求出前i項，而并未給定一個區間，那我們就能想出更快速、方便的方法。

對于任意一個節點，作為右孩子，如果求和時被用到，那它的左兄弟一定也會被用到，那我們就沒必要再用右孩子，因為用他們的父就可以了。

這樣一來，我們就可以把所有有孩子全部去掉

把剩下的節點編號。

如圖，可以發現一些規律：1，3，5，7，9等奇數，區間長度都為1

6，10，14等長度為2

........................

如果我們吧編號換成二進制，就能發現，二進制以1結尾的數字區間長度為1，最后有一個零的區間為2，兩個零的區間為4.

我們利用二進制就能很容易地把編號和區間對應起來。

?

計算前i項和。

需要把當前編號i的數值加進來，把i最右邊的1減掉，直到i變為0.

二進制最后一個1可以通過i&-i得到。

?

更新：

不斷把當前位置i加x，把i的二進制最低非零位對應的冪加到i上。

下面是代碼：

思想想出來挺麻煩，代碼實現很簡單，我都不知道要注釋點啥

向發明這些東西的大佬們致敬

int bit[MAX_N+1]
int n;int sum(int i)
{int gg=0;while(i>0){gg+=bit[i];i-=i&-i;}return gg;
}void add(int i,int x)
{while(i<=n){bit[i]+=x;i+=i&-i;}
}

?