概述

樹狀數組（Binary Indexed Tree，簡稱BIT），是一種數據結構，用于處理區間查詢和更新問題。它是一種可以高效地在對數級別時間復雜度內進行單點更新和區間查詢的數據結構。樹狀數組通常用于解決以下兩類問題：

1. 區間和查詢：給定一個序列，查詢序列中任意區間的和。
2. 區間更新：給定一個序列，對序列中任意區間的值進行增加或減少。

問題引入

給定一個長度為n的數組，完成以下兩種操作：

• 更新：將第x個數加上k；
• 查詢：輸出區間[x, y]內每個數的和。

我們很容易想到一種樸素做法，更新操作直接在原數組上操作，查詢遍歷一下即可，對應的時間復雜度分別為O(1)和O(n)。

當然，你也可能想到用前綴和數組來優化，這樣的話更新操作的時間復雜度就是O(n)，查詢操作的復雜度為O(1)。

可以發現，兩種做法中，要么查詢是O(1)，更新是O(n)；要么更新是O(1)，查詢是O(n)。那么就有沒有一種做法可以綜合一下這兩種樸素做法，然后整體時間復雜度可以降一個數量級呢？有的，對，就是樹狀數組。

lowbit函數

學習樹狀數組之前首先需要了解一下lowbit函數。lowbit函數的功能就是求某一個數的二進制表示中最低的一位1所表示的數值。這個數值一定是2的冪。舉個例子，x = 6，它的二進制為110，那么lowbit(x)就返回2，因為最后一個1表示2。再舉個例子，lowbit(4) = 4。

我們知道，負數的補碼是它的反碼+1。當然，還有一種快捷求法就是，從右往左數第一個1及其右邊的0不動，剩下的位取反。這時候，我們如果讓它和原數進行二進制與操作，就能得到最后的一個1及其后面的0。例如，6的二進制為0110，-6的補碼為1010，它們兩個做與運算就能消掉最后一個1前面的所有位。用代碼表示如下：

int lowbit(int x)
{return x & -x;
}

樹狀數組的思想

首先要明確樹狀數組里存的是什么。假設原數組是arr，我們需要維護一個新的樹狀數組c，c數組里的每一位存的是arr中對應下標開始往前數lowbit(下標)個數的和。例如，c[6]的下標為6，并且lowbit(6) = 2，所以c[6]存的就是arr中從第6項開始往前數2個數的和，即arr[5] + arr[6]。因此，相比前綴和數組，樹狀數組可以說存的是區間和。

查詢

明白了樹狀數組存的是什么，就可以用樹狀數組來求前綴和了。因為查詢操作還是要通過兩個前綴和做差來得到任意區間的和。

因為樹狀數組存的是區間和，我們通過不同的區間拼湊出一個完整的前綴區間就能計算前綴和。還是以6為例，6的二進制為110，可以寫成100 + 10，即4 + 2。根據樹狀數組的定義，c[6]存的是arr[5] + arr[6]。得到第一個區間和后，減去lowbit，即6 - lowbit(6) = 6 - 2 = 4。而c[4]存的是arr中第1項到第4項的和，這是因為lowbit(4) = 4。這兩段拼起來正好得到第6項的前綴和。

因此，用樹狀數組求第x項前綴和可以用下面的代碼表示：

int sum(int x, int c[])
{int res = 0;for (; x > 0; x -= lowbit(x))res += c[x];return res;
}

更新

如果理解了上述過程，我們其實能發現，樹狀數組求前綴和本質上就是將下標展開成二進制，根據二進制位上的1來求和，從而實現對數級別的復雜度。樹狀數組用圖來表示就是像下面這樣。

其中，1到12是樹狀數組的下標，上面的橫條表示了這一項對應arr數組中的區間和。我們從這張圖中可以得到樹狀數組的如下性質：

• 下面層的下標只要補上自己的lowbit值就可以得到上面層的下標(圖中的虛線指出了什么是上面層)。注意，是上面層的下標，而不是上一層的下標，這個性質就是更新操作的依據；

例如，下標6只要加上lowbit(6)，也就是2，就能跳到自己的上面層，也就是8。之所以8是上面層，是因為它們的區間產生了重疊。加上lowbit值會讓最低位的1往高位移動，其所代表的冪會指數增長，遠大于加上的值。所以上面層必定包含下面層。如果不能理解記住這個性質就好。

理解了這一點，就可以明白更新操作了。如果在arr數組上進行更新操作，很簡單，只要修改第x項就可以了。但是樹狀數組表示的是區間和，修改了這一項會影響到很多包含這一項的區間。因此，在c數組上，所有包含第x項的區間和都要修改。

更新了arr的第x項，首先影響到的就是c[x]。因為c[x]所代表的區間和長度至少為1，即必定包含arr[x]。然后就是上面的性質所說的上面層了。我們通過不斷加上lowbit值往上層跳，不斷更新c數組，就能實現對數級別復雜度的更新操作。代碼如下：

void update(int x, int val, int c[], int n)
{for (; x <= n; x += lowbit(x))c[x] += val;
}

代碼實現

輸入格式

第一行輸入兩個整數n和m，分別表示數組長度和操作的次數；

第二行輸入n個整數表示數組；

接下來m行，每行輸入一個字符ch和兩個整數x，y。ch='F'表示查詢x到y這段閉區間的和；ch='S'表示第x個元素加上y。

輸出格式

對于每個查詢，輸出結果。

樣例輸入

5 6
1 2 3 4 5
F 1 3
S 1 2
F 1 3
S 2 3
F 1 2
F 1 5

樣例輸出

6
8
8
20

完整代碼實現如下：

#include <iostream>using namespace std;const int MAX = 1e6;
int c[MAX]; // c[i]表示從第i個元素向前數lowbit(i)個元素，這一段的和，包括c[i]int lowbit(int x)
{return x & -x;
}/*** @brief 求下標為x的前綴和** @param x* @return int*/
int sum(int x, int c[])
{int res = 0;for (; x > 0; x -= lowbit(x))res += c[x];return res;
}/*** @brief 原數組x的位置上的數加上了val，所以要維護c數組** @param x* @param val* @param c* @param n*/
void update(int x, int val, int c[], int n)
{for (; x <= n; x += lowbit(x))c[x] += val;
}int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i++){int x;cin >> x;update(i, x, c, n);}while (m--){int x, y;char ch;cin >> ch >> x >> y;switch (ch){case 'F':cout << sum(y, c) - sum(x - 1, c) << endl;break;case 'S':update(x, y, c, n);break;}}return 0;
}