1．樹狀陣列的原理
在程式設計時，我們需要維護一個一維陣列A的前綴和S，設S[i]=A[1]+A[2]+…+A[i]，
如果我們修改了任意一個元素A[i]的值，則相關的前綴和S[i]、S[i+1]、…、S[n]都會發生變化，若采用傳統的線性順序掃描方法求連續陣列元素的和，則每次修改A[i]后，調整前綴和S的時間復雜度為O(n)，若修改陣列A中元素的頻度為m，則調整前綴和S的時間復雜度為O(m*n)，
為提高維護前綴和的效率，可引入“樹狀陣列”，樹狀陣列通過將線性結構轉換成偽樹狀結構（線性結構只能逐個掃描元素，而樹狀結構可以實作跳躍式掃描），使得修改陣列元素值后，維護前綴和的時間復雜度為O(log2n)，從而大大提高整體效率，
設有陣列A[n]，相應的樹狀陣列為C[n]，當n=9時，其樹形結構如圖1所示，
圖1 樹狀陣列結構示意圖
在圖1中，設黑色陣列元素A[1]~A[8]代表原來的陣列A，紅色陣列元素C[1]~C[8]就代表了樹狀陣列C，若圖中每個結點元素存放其子結點元素值的和，則有
C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
可以發現，樹狀陣列各元素的值是有規律的
C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]; // k為i的二進制中最右端1的位號
例如i =6時，其二進制數為110，最右端1的位置為1，故k =1，C[6]=A[6-2+1]+A[6]；
i = 8時，其二進制數為1000，最右端1的位置為3，故k = 3，C[8]=A[8-8+1]+…+A[8]，
（1）求前綴和，
我們先來看如何利用樹狀陣列C，求A陣列中前i項的和，
例如，i=5時，
S[5]=A[1]+A[2]+A[3]+A[4]+A[5] ;
由圖1知，C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5];
故: S[5]=C[4]+C[5];
序號寫為二進制可得：S[(101)]=C[(100)]+C[(101)]，
再如，i=7時，
S[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ;
由圖1知，C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];
故: S[7]=C[4]+C[6]+C[7];
序號寫為二進制可得：S[(111)]=C[(100)]+C[(110)]+C[(111)];
觀察上面的兩個示例，樹狀陣列其根本實質就是二進制的應用，
由此，可將求前綴和的操作寫成如下函式：
int getsum(int i)
{
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
其中，函式lowbit(i)的回傳值為2k，k為i的二進制中最右端1的位號，
下面以i=7為例模擬函式getsum(7)的執行程序，
i=7（二進制數為111），res+=C[7]=C[7]， lowbit(7)=001（二進制表示，對應1），i=7-1=6；
i=6（二進制數為110），res+=C[6]， lowbit(6)=010（二進制表示，對應2），i=6-2=4；
i=4（二進制數為100），res+=C[4]， lowbit(4)=100（二進制表示，對應4），i=4-4=0；
i=0，結束回圈，回傳res（=C[7]+C[6]+C[4]），
這樣，利用樹狀陣列能快速求任意區間[a,b]的和：A[a] + A[a+1] +…+ A[b]，直接呼叫getsum(b)-getsum(a-1)即可，
（2）單點更新，
下面我們再討論樹狀陣列如何生成并維護，
當修改陣列A中的某一個元素A[i]的值時 應當如何更新陣列樹狀C呢？
當修改A[i]的值時，可以從C[i]往根結點一路上溯，調整這條路線上的所有C[k]即可，
例如，修改A[1]時，需要向上更新C[1] 、C[2]、C[4]、C[8]，表示成二進制對應為：
C[(001)]、C[(010)]、C[(100)]、C[(1000)]
再如，修改A[5]時，需要向上更新C[5] 、C[6]、C[8]，表示成二進制對應為：
C[(101)]、C[(110)]、C[(1000)]
觀察上面的兩個示例，單點更新其實與求前綴和互為逆運算，
由此，可將單點更新的操作寫成如下函式：
void update(int i,int value) // 修改A[i]值使其增加value后，更新樹狀陣列
{
while (i<=n)
{
c[i]+=value;
i+=lowbit(i);
}
}
下面以修改A[5]為例，模擬函式update(5,val)的執行程序，
i=5（二進制數為101），C[5]+=val，lowbit(5)=001（二進制表示，對應1），i=5+1=6；
i=6（二進制數為110），C[6]+=val，lowbit(6)=010（二進制表示，對應2），i=6+2=8；
i=8（二進制數為1000），C[8]+=val，lowbit(8)=10000（二進制表示，對應16），i=8+16=24；
i=24>n，結束回圈，回圈期間，C[5]、C[6]、C[8]進行了更新，
有了單點更新函式，就很容易根據給定陣列A構造對應的樹狀陣列C了，初始時，令陣列C的全部元素值為0，依次用陣列A的元素值A[1]~A[n]，呼叫函式update(I,A[i])，即可構造出對應的樹狀陣列C，
（3）lowbit函式的實作，
函式lowbit(i)的回傳值為2k，k為i的二進制中最右端1的位號，這可以用一個運算式i&(-i)簡單地實作，即2^k = i&(-i) ，
這里利用了負數的存盤特性，在計算機中負整數是以補碼存盤的，對于整數運算 x&(-x)有：
1）當i為0時，即 0 & 0，結果為0；
2）當i為奇數時，最后一個位元位為1，取反加1沒有進位，故x和-x除最后一位外前面的位正好相反（按位與結果為0），最后1位都為1，按位與后結果為1，
3）當i為偶數，且為2的m次方時，x的二進制表示中只有一位是1（設為從右往左的第m+1位），其右邊有m位0，故x取反加1后，從右到左第有m個0，第m+1位及其左邊全是1，這樣，x& (-x) 得到的就是x，
4）當i為偶數，卻不為2的m次方的形式時，可以寫作i= y * (2^k)，其中，y的最低位為1，實際上就是把i用一個奇數左移k位來表示，這時，i的二進制表示最右邊有k個0，從右往左第k+1位為1，當對i取反時，最右邊的k位0變成1，第k+1位變為0；再加1，最右邊的k位就又變成了0，第k+1位因為進位的關系變成了1，左邊的位因為沒有進位，正好和i原來對應的位上的值相反，二者按位與，得到：第k+1位上為1，左邊右邊都為0，結果為2^k，
2．樹狀陣列的應用
下面我們通過實體介紹樹狀陣列的應用，
2.1 單點更新、區間查詢
對給定陣列的某個元素進行更新，然后對區間的和值進行查詢，
例1 【模板】樹狀陣列 1
本題選自洛谷題庫（https://www.luogu.com.cn/problem/P3374）
題目描述
已知一個數列，你需要進行下面兩種操作：
將某一個數加上x
求出某區間每一個數的和
輸入格式
第一行包含兩個正整數 n,m，分別表示該數列數字的個數和操作的總個數，
第二行包含 n 個用空格分隔的整數，其中第 i 個數字表示數列第 i 項的初始值，
接下來 m 行每行包含3 個整數，表示一個操作，具體如下：
1 x k 含義：將第 x 個數加上 k
2 x y 含義：輸出區間 [x,y]內每個數的和
輸出格式
輸出包含若干行整數，即為所有操作 22 的結果，
輸入樣例
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
輸出樣例
14
16
（1）編程思路，
典型的樹狀陣列應用模板題，直接撰寫并呼叫前面介紹的三個函式即可，
（2）源程式，
#include <stdio.h>
#include <string.h>
int n;
int c[500001];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int value)
{
while (i<=n)
{
c[i]+=value;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
int main()
{
int m;
scanf("%d%d",&n,&m);
memset(c, 0, sizeof c);
int i,p,x,y;
for (i=1;i<=n;i++)
{
scanf("%d",&x);
update(i,x);
}
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&p,&x,&y);
if (p==1) update(x,y);
else printf("%d\n",getsum(y)-getsum(x-1));
}
return 0;
}
2.2 區間更新、單點查詢
設有陣列A[n]，若要將區間[x,y]內的所有元素的值全部加上k或者減去k，然后查詢某個元素A[i]的值，這種時候該怎么做呢？
如果直接采用陣列A的初始各元素值建立樹狀陣列C，然后將[x,y]區間內每個值都更新，最后利用getsum(i)-getsum(i-1)得到待查詢元素A[i]的值，這種辦法的復雜度肯定是不行的，最好的辦法是引入差分，利用差分建樹，
設有陣列A[n+1]，且令A[0]=0，利用公式 B[i]=A[i]-A[i-1] (1≤i≤n) 建立差分陣列B，
顯然有 A[i]=B[1]+B[2]+B[3]+ …+B[i]
=A[1]-A[0]+A[2]-A[1]+…+A[i]-A[i-1] =A[i]
這樣，待查詢陣列元素A[i]的值就是差分陣列B的前i項的和，
當陣列A的區間[x,y]內的所有元素（A[x]~A[y]）的值全部加上k或者減去k時，區間內的元素的差值是不變的，因此對應B陣列只有B[x] 加上k或者減去k、B[y+1] 減去k或加上k，其余元素值不變，
這樣，我們用差分陣列B構造樹狀陣列C，每次區間修改就只進行兩次單點修改，
例2 【模板】樹狀陣列 2
本題選自洛谷題庫（https://www.luogu.com.cn/problem/P3368）
題目描述
已知一個數列，你需要進行下面兩種操作：
將某區間每一個數加上x；
求出某一個數的值，
輸入格式
第一行包含兩個整數 N、M，分別表示該數列數字的個數和操作的總個數，
第二行包含 N 個用空格分隔的整數，其中第 i 個數字表示數列第 i 項的初始值，
接下來 M 行每行包含 2 或 4個整數，表示一個操作，具體如下：
操作 1： 格式：1 x y k 含義：將區間 [x,y]內每個數加上k；
操作 2： 格式：2 x 含義：輸出第 x 個數的值，
輸出格式
輸出包含若干行整數，即為所有操作 22 的結果，
輸入樣例
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
輸出樣例
6
10
（1）編程思路，
典型的區間更新、單點查詢模板題，利用陣列相鄰元素的差值構造樹狀陣列，
（2）源程式，
#include <stdio.h>
#include <string.h>
int n;
int a[500001],c[500001];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int value)
{
while (i<=n)
{
c[i]+=value;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
int main()
{
int m,i;
scanf("%d%d",&n,&m);
memset(c, 0, sizeof c);
for (i = 1; i<=n; i++)
{
scanf("%d",&a[i]);
update(i,a[i] - a[i-1]);
}
for (i=1;i<=m;i++)
{
int f,x,y,k;
scanf("%d",&f);
if (f==1)
{
scanf("%d%d%d",&x,&y,&k);
update(x,k);
update(y+1,-k);
}
if (f==2)
{
scanf("%d",&x);
printf("%d\n",getsum(x));
}
}
return 0;
}
例3 Color the ball
本題選自杭州電子科技大學OJ題庫（http://acm.hdu.edu.cn/showproblem.php?pid=1556），
Problem Description
N個氣球排成一排，從左到右依次編號為1,2,3....N，每次給定2個整數a b(a <= b),lele便為騎上他的“小飛鴿”牌電動車從氣球a開始到氣球b依次給每個氣球涂一次顏色，但是N次以后lele已經忘記了第I個氣球已經涂過幾次顏色了，你能幫他算出每個氣球被涂過幾次顏色嗎？
Input
每個測驗實體第一行為一個整數N,(N <= 100000).接下來的N行，每行包括2個整數a b(1 <= a <= b <= N)，
當N = 0，輸入結束，
Output
每個測驗實體輸出一行，包括N個整數，第I個數代表第I個氣球總共被涂色的次數，
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
（1）編程思路，
設有陣列A[N+1]，A[i]的值表示編號為i的氣球被涂色的次數，初始時元素值全為0，從氣球a開始到氣球b依次給每個氣球涂一次顏色相當于對陣列A的區間[a,b]中的每個元素加1，若定義陣列A的差值陣列B（差值陣列的初始值顯然也全為0），則對陣列A的區間[a,b]中的各元素進行加1修改操作，只需對應對陣列B的兩個元素B[a]和B[b+1]進行單點修改即可，其中B[a]加1，B[b+1]減1，
根據樹狀陣列的原理，A[i]的值就是差值陣列B的前i項的和，呼叫函式getsum(i)即可，
（2）源程式，
#include <stdio.h>
#include <string.h>
int n;
int c[100001];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int value)
{
while (i<=n)
{
c[i]+=value;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
int main()
{
while (scanf("%d",&n) && n!=0)
{
memset(c, 0, sizeof c);
for (int i=1; i<=n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
update(a, 1);
update(b + 1, -1);
}
for (int i = 1; i<n; i++)
{
printf("%d ",getsum(i));
}
printf("%d\n",getsum(n));
}
return 0;
}
例4 Matrix
本題選自北京大學OJ題庫（http://poj.org/problem?id=2155），
Description
Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
Input
The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.
Output
For each querying output one line, which has an integer representing A[x, y].
There is a blank line between every two continuous test cases.
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
0
0
1
（1）編程思路，
本題的題意是給定N*N矩陣A，矩陣中的元素值非0即1，初始時元素值全為0，對矩陣中的子矩陣[x1, y1, x2, y2]（x1、y1表示子矩陣左上角元素下標，x2、y2表示子矩陣右下角元素坐標）中的各元素進行變反操作（0變1，1變0），查詢矩陣中元素A[x][y]的值，
根據題目中矩陣A的元素值不是 1 就是 0這一特點，我們只需記錄每個元素值改變過幾次，即可得到每個元素的值，
由例3可知，當陣列是一維時，若要修改[x,y]區間的值，只需修改x和y+1這兩個點的值（將點x值加1，點y+1值減1），查詢k點的值時，呼叫函式getsum(k)即可，
當陣列為二維時，解決方法類同一維，要修改范圍[x1, y1, x2, y2]，只需修改這四個點：(x1,y1), (x1,y2+1), (x2+1,y1), (x2+1,y2+1)，查詢點(x,y)的值時，呼叫函式getsum(x, y)，
按樹狀陣列的原理，需要將單點修改和求前綴和函式修改為二維的處理情況，
（2）源程式，
#include <stdio.h>
#include <string.h>
int n;
int c[1001][1001];
int lowbit(int x)
{
return x&(-x);
}
void update(int x, int y, int value)
{
for (int i = x; i<= n; i+=lowbit(i))
for (int j=y; j<= n; j+=lowbit(j))
c[i][j]+=value;
}
int getsum(int x, int y)
{
int res = 0;
for (int i = x; i>0; i-=lowbit(i))
for (int j = y; j > 0; j -= lowbit(j))
res += c[i][j];
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m,x1,y1,x2,y2;
scanf("%d%d", &n, &m);
memset(c, 0, sizeof(c));
char op[5];
while (m--)
{
scanf("%s%d%d", op, &x1, &y1);
if (op[0] == 'C')
{
scanf("%d%d", &x2, &y2);
update(x1, y1, 1);
update(x1, y2+1, 1);
update(x2+1, y1, 1);
update(x2+1, y2+1, 1);
}
else
{
printf("%d\n", getsum(x1,y1) %2);
}
}
printf("\n");
}
return 0;
}
例5 Flowers
本題選自杭州電子科技大學OJ題庫（http://acm.hdu.edu.cn/showproblem.php?pid=4325），
Problem Description
As is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many flowers will bloom in the garden in a specific time. But there are too many flowers in the garden, so he wants you to help him.
Input
The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times.
In the next N lines, each line contains two integer Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.
Output
For each case, output the case number as shown and then print M lines. Each line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.
Sample Input
2
1 1
5 10
4
2 3
1 4
4 8
1
4
6
Sample Output
Case #1:
0
Case #2:
1
2
1
（1）編程思路1，
本題的題意是：有n朵花和m個時間點，第i朵花正在開放的時間是si和ti，問在第mi個時間點有多少朵花正在開放？
類同例3的編程思路，初始時所有時間點都沒有花兒開放，第i朵花正在開放的時間是si和ti，相當于對區間[si,ti]中每個元素加1（有一朵花開放），問在第mi個時間點有多少朵花正在開放，呼叫函式getsum(mi)得到結果，
先定義樹狀陣列的大小為int c[100005];，仿例3撰寫如下的源程式，
（2）可以Accepted但存在缺陷的源程式，
#include <stdio.h>
#include <string.h>
int n;
int c[100005];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int value)
{
while (i<=100005)
{
c[i]+=value;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
for (int k=1;k<=t;k++)
{
memset(c, 0, sizeof c);
int m;
scanf("%d%d",&n,&m);
int i,s,t;
for (i=1; i<=n; i++)
{
scanf("%d%d",&s,&t);
update(s, 1);
update(t + 1, -1);
}
printf("Case #%d:\n",k);
for (i = 1; i<=m; i++)
{
scanf("%d",&t);
printf("%d\n",getsum(t));
}
}
return 0;
}
這個源程式提交給OJ系統后，可以Accepted，但實際上這個程式是存在問題的，因為按題意花開的開始時間和結束時間Si 和Ti資料范圍為1 <= Si <= Ti <= 10^9，而程式中定義的陣列C，最大為100005，之所以Accepted，是因為測驗資料集太弱，與題目中資料說明存在偏差，如果測驗資料中輸入的Si或Ti大于10^5，程式運行會出錯，但將陣列C定義為int C[10e9+1]是不現實地，因為陣列C會過大，無法通過編譯，
（3）編程思路2，
由題意，輸入的Si 和Ti資料范圍為1 <= Si <= Ti <= 10^9，而花兒朵數N的范圍為1 <= N <= 10^5，每朵花開放有兩個時間點，查詢時間點個數M的范圍為1 <= N <= 10^5，因此可以想辦法將1~ 10^9范圍的資料縮小到1~3*10^5的范圍，為了將較大的資料范圍縮小到一個較小的資料范圍，可以進行離散化處理，
離散化的處理方法是：將原始資料按從小到大順序排列，然后對資料編名次（相同的資料名次相同），然后各原始資料用其名次表示，
以測驗樣例為例說明，
例如，兩朵花的開放時間點分別為1、4和4、8，3個查詢時間點為1、4、6，這7個時間點按從小到大排序為1、1、4、4、6、8，相應名次為1、1、2、2、3、4，這樣離散化后，1用1表示，4用2表示，6用3表示，8用4表示，
又如，3朵花的開放時間點分別為100、420，420、8900和123456789、987654321，4個查詢時間點為10、400、6000和87654，這10個時間點按從小到大排序為：
10、100、400、420、420、6000、8900、87654、123456789、987654321，相應名次為1、2、3、4、4、5、6、7、8、9，這樣離散化后，10用1表示，100用2表示，400用3表示，420用4表示，…，987654321用5表示，
離散化之后就可以采用樹狀陣列解決問題了，
（4）正確進行離散化處理的源程式，
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
int id,x;
};
struct node a[300005];
int c[300005],rankk[300005];
bool cmp(struct node a,struct node b)
{
return a.x<b.x;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int n,int value)
{
while (i<=n)
{
c[i]+=value;
i+=lowbit(i);
}
}
int getsum(int i)
{
int res = 0;
while(i > 0)
{
res += c[i];
i -= lowbit(i);
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
for (int k=1;k<=t;k++)
{
int n,m;
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
memset(rankk,0,sizeof(rankk));
int temp=2*n+m,i;
for (i=1;i<=temp;i++)
{
scanf("%d",&a[i].x);
a[i].id=i;
}
sort(a+1,a+1+temp,cmp);
int cnt=1;
rankk[a[1].id]=cnt;
for (i=2;i<=temp;i++)
{
if(a[i].x==a[i-1].x) // 判重
rankk[a[i].id]=cnt;
else
rankk[a[i].id]=++cnt;
}
for (i=1;i<2*n;i+=2)
{
update(rankk[i],cnt,1);
update(rankk[i+1]+1,cnt,-1);
}
printf("Case #%d:\n",k);
for (i=2*n+1;i<=temp;i++)
{
printf("%d\n",getsum(rankk[i]));
}
}
return 0;
}
2.3 區間更新、區間查詢
由前面介紹的樹狀陣列原理可知，樹狀陣列的本質就是實作時間復雜度為O(log2n) 的“單點更新，區間查詢”，將其進行變形，利用差值建樹狀陣列，可以實作“區間更新，單點查詢”，那么，如何實作“區間更新，區間查詢”呢？
設有陣列a[n+1]，且令a[0]=0，利用公式 c[i]=a[i]-a[i-1] (1≤i≤n) 建立差分陣列c，
觀察式子：
a[1]+a[2]+...+a[n]
=(a[1]-0)+(a[1]-0+a[2]-a[1])+…+ (a[1]-0 +a[2]-a[1]+…+a[n]-a[n-1])
= (c[1]) + (c[1]+c[2]) + … + (c[1]+c[2]+ … +c[n])
= n*c[1] + (n-1)*c[2] +... +c[n]
= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n])
再建立一個樹狀陣列c2，其中c2[i] = (i-1)*c[i]，由此，
a[1]+a[2]+...+a[n] = n* getsum (c,n) - getsum (c2,n)
// 其中，getsum (c,n)表示樹狀陣列c的前n項的和
而x到y的區間和即為：
（y* getsum (c,y) - getsum (c2,y)）- （(x-1)* getsum (c,x-1) - getsum (c2,x-1)）
例6 【模板】線段樹 1
本題選自洛谷題庫（https://www.luogu.com.cn/problem/ P3372）
題目描述
已知一個數列，你需要進行下面兩種操作：
將某區間每一個數加上 k，
求出某區間每一個數的和，
輸入格式
第一行包含兩個整數 n, m，分別表示該數列數字的個數和操作的總個數，
第二行包含 n 個用空格分隔的整數，其中第 i 個數字表示數列第 i 項的初始值，
接下來m行每行包含3或4個整數，表示一個操作，具體如下：
1 x y k：將區間 [x, y]內每個數加上 k，
2 x y：輸出區間 [x,y] 內每個數的和，
輸出格式
輸出包含若干行整數，即為所有操作 2 的結果，
輸入樣例
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
輸出樣例
11
8
20
（1）編程思路，
典型的區間更新、區間查詢模板題，利用陣列相鄰元素的差值構造樹狀陣列c1，再利用樹狀陣列c1構造樹狀陣列c2，
（2）源程式，
#include <stdio.h>
#include <string.h>
typedef long long LL;
#define MAXN 100001
LL n;
LL c1[MAXN],c2[MAXN];
LL lowbit(LL x)
{
return x&(-x);
}
void update(LL x,LL value,LL *c)
{
while(x<=n)
{
c[x]+=value;
x+=lowbit(x);
}
}
LL getsum(LL x,LL *c)
{
LL sum=0;
while(x>0)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
int q,op;
LL x,y,d;
scanf("%lld%d",&n,&q);
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
y=0;
for (int i=1;i<=n;++i)
{
scanf("%lld",&x);
d=x-y;
update(i,d,c1);
update(i,(i-1)*d,c2);
y=x;
}
for(int i=0;i<q;++i)
{
scanf("%d",&op);
if (op==1)
{
scanf("%lld%lld%lld",&x,&y,&d);
update(x,d,c1);
update(y+1,-d,c1);
update(x,(x-1)*d,c2);
update(y+1,-y*d,c2);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",getsum(y,c1)*y-getsum(x-1,c1)*(x-1) -getsum(y,c2)+getsum(x-1,c2));
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/236880.html
標籤：C
上一篇：Vscode下載與配置（C語言）