假設我們現在拿到了一個非常大的數組，對於這個數組裡面的數字要反覆不斷地做兩個操作。

1、（query）隨機在這個數組中選一個區間，求出這個區間所有數的和。

2、（update）不斷地隨機修改這個數組中的某一個值。

時間複雜度：

枚舉：

枚舉L~R的每個數並累加。

• query：O（n）

找到要修改的數直接修改。

• update：O（1）

如果query與update要做很多很多次，query的O（n）會被卡住，所以時間複雜度會非常慢。那麼有沒有辦法把query的時間複雜度降成O（1）呢？其中一種方法如下：

• 先建立一個與a數組一樣大的數組。

• s[1]=a[1];s[2]=a[1]+a[2];s[3]=a[1]+a[2]+a[3];...;s[n]=a[1]+a[2]+a[3]+...+a[n]（在s數組中存入a的前綴和）

• 此時a[L]+a[L+1]+...+a[R]=s[R]-s[L-1]，query的時間複雜度降為O（1）。
• 但若要修改a[k]的值，隨之也需修改s[k],s[k+1],...,s[n]的值，時間複雜度升為O（n）。

前綴和：

query：O（1）

update：O（n）

• 我們發現，當我們想盡方法把其中一個操作的時間複雜度改成O（1）後，另一個操作的時間複雜度就會變為O（n）。當query與update的操作特別多時，不論用哪種方法，總體的時間複雜度都不會特別快。
• 所以，我們將要討論一種叫線段樹的數據結構，它可以把這兩個操作的時間複雜度平均一下，使得query和update的時間複雜度都落在O（n log n）上，從而增加整個算法的效率。

線段樹

假設我們拿到了如下長度為6的數組：

在構建線段樹之前，我們先闡述線段樹的性質：

1、線段樹的每個節點都代表一個區間。

2、線段樹具有唯一的根節點，代表的區間是整個統計範圍，如[1,N]。

3、線段樹的每個葉節點都代表一個長度為1的元區間[x,x]。

4、對於每個內部節點[l,r]，它的左子結點是[l,mid]，右子節點是[mid+1,r]，其中mid=(l+r)/2（向下取整）。

依照這個數組，我們構建如下線段樹（結點的性質為sum）：

若我們要求[2-5]區間中數的和：

若我們要把a[4]改為6：

• 先一層一層找到目標節點修改，在依次向上修改當前節點的父節點。

接下來的問題是：如何保存這棵線段樹？

• 用數組存儲。

若我們要取node結點的左子結點（left）與右子節點（right），方法如下：

• left=2*node+1
• right=2*ndoe+2

舉結點5為例（左子結點為節點11，右子節點為節點12）：

• left₅=2*5+1=11
• right₅=2*5+2=12

接下來給出建樹的代碼：

#include<bits/stdc++.h>
using namespace std; 
const int N = 1000;
int a[] = {1, 3, 5, 7, 9, 11};
int size = 6;
int tree[N] = {0};
//建立範圍為a[start]~a[end] 
void build(int a[], int tree[], int node/*當前節點*/, int start, int end){
 //遞歸邊界(即遇到葉子節點時) 
 if (start == end){
 //直接存儲a數組中的值 
 tree[node] = a[start];
 } 
 else {
 //將建立的區間分成兩半 
 int mid = (start + end) / 2;
 
 int left = 2 * node + 1;//左子節點的下標 
 int right = 2 * node + 2;//右子節點的下標 
 
 //求出左子節點的值(即從節點left開始,建立範圍為a[start]~a[mid])
 build(a, tree, left, start, mid);
 //求出右子節點的值(即從節點right開始,建立範圍為a[start]~a[mid])
 build(a, tree, right, mid+1, end);
 
 //當前節點的職位左子節點的值加上右子節點的值 
 tree[node] = tree[left] + tree[right];
 }
}
int main(){
 //從根節點(即節點0)開始建樹,建樹範圍為a[0]~a[size-1]
 build(a, tree, 0, 0, size-1);
 
 for(int i = 0; i <= 14; i ++)
 printf("tree[%d] = %d\\n", i, tree[i]);
 
 return 0;
}

運行結果：

update操作：

• 確定需要改的分支，向下尋找需要修改的節點，再向上修改節點值。
• 與建樹的函數相比，update函數增加了兩個參數x，val，即把a[x]改為val。

例：把a[x]改為6（代碼實現）

void update(int a[], int tree[], int node, int start, int end, int x, int val){
 //找到a[x],修改值 
 if (start == end){
 a[x] = val;
 tree[node] = val;
 }
 
 else {
 int mid = (start + end) / 2;
 
 int left = 2 * node + 1;
 int right = 2 * node + 2;
 
 if (x >= start && x <= mid) {//如果x在左分支 
 update(a, tree, start, mid, x, val);
 }
 else {//如果x在右分支 
 update(a, tree, right, mid+1, end, x, val);
 }
 
 //向上更新值 
 tree[node] = tree[left] + tree[right]; 
 } 
}
在主函數中調用：
//把a[x]改成6
update(a, tree, 0, 0, size-1, 4, 6);

運行結果：

query操作：

• 向下依次尋找包含在目標區間中的區間，並累加。
• 與建樹的函數相比，query函數增加了兩個參數L，Rl，即把求a的區間[L,R]的和。

例：求a[2]+a[3]+...+a[5]的值（代碼實現）

int query(int a[], int tree[], int node, int start, int end, int L,int R){
 //若目標區間與當時區間沒有重疊,結束遞歸返回0 
 if (start > R || end < L){
 return 0;
 }
 
 //若目標區間包含當時區間,直接返回節點值 
 else if (L <=start && end <= R){
 return tree[node];
 }
 
 else {
 int mid = (start + end) / 2;
 
 int left = 2 * node + 1;
 int right = 2 * node + 2;
 
 //計算左邊區間的值 
 int sum_left = query(a, tree, left, start, mid, L, R);
 //計算右邊區間的值 
 int sum_right = query(a, tree, right, mid+1, end, L, R);
 
 //相加即為答案 
 return sum_left + sum_right;
 } 
}
在主函數中調用：
//求區間[2,5]的和
int ans = query(a, tree, 0, 0, size-1, 2, 5);
printf("ans = %d", ans); 

運行結果：

最後，獻上完整的代碼：

#include<bits/stdc++.h>
using namespace std; 
const int N = 1000;
int a[] = {1, 3, 5, 7, 9, 11};
int size = 6;
int tree[N] = {0};
//建立範圍為a[start]~a[end] 
void build(int a[], int tree[], int node/*當前節點*/, int start, int end){
 //遞歸邊界(即遇到葉子節點時) 
 if (start == end) {
 //直接存儲a數組中的值 
 tree[node] = a[start];
 } 
 else {
 //將建立的區間分成兩半 
 int mid = (start + end) / 2;
 
 int left = 2 * node + 1;//左子節點的下標 
 int right = 2 * node + 2;//右子節點的下標 
 
 //求出左子節點的值(即從節點left開始,建立範圍為a[start]~a[mid])
 build(a, tree, left, start, mid);
 //求出右子節點的值(即從節點right開始,建立範圍為a[start]~a[mid])
 build(a, tree, right, mid+1, end);
 
 //當前節點的職位左子節點的值加上右子節點的值 
 tree[node] = tree[left] + tree[right];
 }
}
void update(int a[], int tree[], int node, int start, int end, int x, int val){
 //找到a[x],修改值 
 if (start == end){
 a[x] = val;
 tree[node] = val;
 }
 
 else {
 int mid = (start + end) / 2;
 
 int left = 2 * node + 1;
 int right = 2 * node + 2;
 
 if (x >= start && x <= mid) {//如果x在左分支 
 update(a, tree, left, start, mid, x, val);
 }
 else {//如果x在右分支 
 update(a, tree, right, mid+1, end, x, val);
 }
 
 //向上更新值 
 tree[node] = tree[left] + tree[right]; 
 } 
}
//求a[L]~a[R]的區間和 
int query(int a[], int tree[], int node, int start, int end, int L,int R){
 //若目標區間與當時區間沒有重疊,結束遞歸返回0 
 if (start > R || end < L){
 return 0;
 }
 
 //若目標區間包含當時區間,直接返回節點值 
 else if (L <=start && end <= R){
 return tree[node];
 }
 
 else {
 int mid = (start + end) / 2;
 
 int left = 2 * node + 1;
 int right = 2 * node + 2;
 
 //計算左邊區間的值 
 int sum_left = query(a, tree, left, start, mid, L, R);
 //計算右邊區間的值 
 int sum_right = query(a, tree, right, mid+1, end, L, R);
 
 //相加即為答案 
 return sum_left + sum_right;
 } 
}
int main(){
 //從根節點(即節點0)開始建樹,建樹範圍為a[0]~a[size-1]
 build(a, tree, 0, 0, size-1);
 
 for(int i = 0; i <= 14; i ++)
 printf("tree[%d] = %d\\n", i, tree[i]);
 printf("\\n"); 
 
 //把a[x]改成6
 update(a, tree, 0, 0, size-1, 4, 6); 
 
 for(int i = 0; i <= 14; i ++)
 printf("tree[%d] = %d\\n", i, tree[i]);
 printf("\\n");
 
 //求區間[2,5]的和
 int ans = query(a, tree, 0, 0, size-1, 2, 5);
 printf("ans = %d", ans); 
 
 return 0;
}

運行結果：

胡哪有學習的視頻鏈接：https://www.bilibili.com/video/av47331849?from=search&seid=17500480857975716688

原文：https://www.cnblogs.com/zhengchang/p/xianduanshu.html

鳴謝作者：小仙女本仙