【令人頭秃的線段樹】線段樹入門題目詳解（代碼逐句分析）

平時在我們解決區間和問題時，我們用的比較多的算法是字首和。使用字首和的話在解題過程中能夠降低時間複雜度，是一個比較常見的算法。但是，如果資料區間的數字會進行改動，那麼我們就會發現，字首和算法在這裡就不好使了，是以，我們今天需要通過介紹一下一個新的資料結構----線段樹。

在此說明，由于篇幅以及筆者能力有限，本篇部落格将不介紹線段樹的基本定義，建議在觀看其它線段樹基本概念的部落格後再通過本部落格來進行進一步加深對線段樹的了解。

題目情景引入

Acwing 動态求連續區間和

給定 n 個數組成的一個數列，規定有兩種操作，一是修改某個元素，二是求子數列 [a,b] 的連續和。

輸入格式
第一行包含兩個整數 n 和 m，分别表示數的個數和操作次數。

第二行包含 n 個整數，表示完整數列。

接下來 m 行，每行包含三個整數 k,a,b （k=0，表示求子數列[a,b]的和；k=1，表示第 a 個數加 b）。

數列從 1 開始計數。

輸出格式
輸出若幹行數字，表示 k=0 時，對應的子數列 [a,b] 的連續和。

資料範圍
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n
輸入樣例：
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
輸出樣例：
11
30
35
           

不難發現，如果這道題使用字首和的話，每進行一次資料的修改都需要更新一次字首和數組，那麼代碼的時間複雜度就會高起來了，是以我們舍棄字首和算法，使用線段樹解題。

在這裡需要說明的是，如果想要熟悉線段樹，光看本篇部落格是遠遠不夠的，還需要自己多加練習。

那麼接下來我們來看看本題的ac代碼

注釋：a<<1=a2 ; a<<1|1=a2+1 ; a>>1=a/2 ; l + r >> 1=(l+r)/2;

以上寫法為位運算知識

#include<iostream>
#include <utility>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define ll long long
#define fi first
#define se second
using namespace std;
typedef  pair<int, int> PII;

const int N = 100010;
int n, m;

int w[N];//用來記錄每一個點的值

struct node//建立線段樹數組
{
	int l, r;//左右區間
    
	int sum;//總和
}tr[N * 4];

void push_up(int u)//利用左右兒子來求區間和
{
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}


/*下面三個函數的u都是在主使用時輸入1，用來進行線段樹的向後查找*/


void build(int u, int l, int r)//建樹函數，u是目前點編号，l和r代表這個節點代表的區間範圍
{
	if (l == r)tr[u] = { l,r,w[r] };
	else
	{
		tr[u] = { l,r };
		int mid = l + r >> 1;
		build(u << 1, l, mid);//遞歸求左兒子
		build(u << 1 | 1, mid + 1, r);//遞歸求右兒子
		push_up(u);//利用左右兒子來計算一下sum
	}
}

int query(int u, int l, int r)//查找l~r區域的和的函數
{
	if (l <= tr[u].l && r >= tr[u].r)return tr[u].sum;//線段樹被切的區域在l和r内了就把這一塊全加上
	int mid = tr[u].l + tr[u].r >> 1;//取個中點準備二分
	int sum = 0;
	if (mid >= l)sum += query(u << 1, l, r);//切塊判斷左兒子區域是否有與l~r重合的區域
	if (r >= mid + 1)sum += query(u << 1 | 1, l, r);//判斷右兒子

		//這裡的遞歸函數會一直切下去，除非線段區域與l~r不重合

	return sum;//傳回上一層把每一段sum加起來就是要求的區域的和
	
}


void modify(int u, int x, int v)//把第x個數修改為v
{
	if (tr[u].l == tr[u].r)//此時的l和r都為x，代表找到這個葉節點了
	{
		tr[u].sum += v;//修改，這裡的線段長度就是一個單獨的點了
	}
	else
	{
		int mid = tr[u].l + tr[u].r >> 1;//開始二分
		if (x <= mid)//尋找x點是在現在這條線段的左半邊還是右半邊，在哪邊遞歸切哪邊的線段
		{
			modify(u << 1, x, v);
		}
		else
		{
			modify(u << 1 | 1, x, v);
		}

		push_up(u);//此時左右兒子都已經遞歸更新完了，來更新一下父親，一路遞歸到最長的線段，即所有資料更新完成
	}
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> w[i];
	}
	build(1, 1, n);
	while (m--)
	{
		int k, a, b;
		cin >> k >> a >> b;
		if (k!=0)
		{
			modify(1, a, b);
		}
		else
		{
			cout << query(1, a, b) << endl;
		}
	}
}

int main()
{
	solve();
	return 0;
}


           

到這裡，這道題目就這麼輕松的解決啦（其實也不輕松 ）。

作者：Avalon·Demerzel，如果本篇部落格有幫到你的話就留下個贊吧。