線段樹

一.概念（構建）

線段樹是一種基于二分思想的完全二叉樹，用于維護一段資料或陣列，并且使得所有操作的時間復雜度盡量維持在O(nlogn)，
對于未安排資料的節點都選擇默認為0，且每一個節點存盤的值都是左右孩子進行一些操作的結果（葉節點除外），

1.代碼實作

其實可以直接以陣列實作，但為了實作再存盤原陣列左右區間的值，就使用結構體實作線段樹

#include<iostream>
using namespace std;

const int N = 1e4 +5;
int arr[N];

struct segmentTree{
	int l,r;
	int val;
}tree[4*N]; 

void build(int p,int l,int r) {
	tree[p].l = l;
	tree[p].r = r;
	//終止條件
	if(l==r) {
		tree[p].val = arr[l];
	} 
	else {
		//本質上是遞回的程序
		int mid = (l+r)/2;
		build(2*p+1,l,mid);
		build(2*p+2,mid+1,r);
		tree[p].val = tree[2*p+1].val + tree[2*p+2].val;
	}
}

int main( ) {
	for(int i=0;i<=5;i++) {
		cin>>arr[i];
	}
	build(0,0,5);
	for(int i=0;i<15;i++) {
		printf("tree[%d,%d]=%d\n",tree[i].l,tree[i].r,tree[i].val);
	}
	return 0;
}

2.運行結果

tree后面跟著的是區間值，一些未進入的結點，全部都初始化為0

二.基本操作

1.查詢（單點 or 區間）

查詢區間和線段樹節點區間相交的不同情況：

1. 查詢區間完全包含線段樹節點區間------------直接回傳該節點tree[p].sum
2. 查詢區間和線段樹節點左孩子有交集---------往下遞回query(2*p+1,L,R)
3. 查詢區間和線段樹節點右孩子有交集---------往下遞回query(2*p+2,L,R)

單點查詢就是區間查詢的特殊情況，此時L = R，對以下代碼稍微修改一下就可以了

int query(int p,int L,int R) {
	int sum = 0;
	//終止條件
	if(tree[p].l>R||tree[p].r<L)
		sum = 0;//不在范圍內直接回傳
	else if(tree[p].l>=L&&R>=tree[p].r)
		sum += tree[p].val;//包含其中直接回傳這個節點的值
	else {	
	    //以上兩種情況都不包含則是有交集的情況，對左右孩子都遞回，不符合會直接回傳
		int mid  = (L+R)/2;
		sum += query(2*p+1,L,R);
		sum += query(2*p+2,L,R);
	}
	return sum;
}

測驗實體

2.單點修改

對單點進行修改就是對于單點查詢做一點修改，在查詢到修改節點值之后，再更新每個祖先節點的值，

//單點修改 
void update(int p,int ind,int val) {
	if(ind < tree[p].l||ind > tree[p].r ) 
		return;
	else if(tree[p].r == tree[p].l) {
		tree[p].val = val;
	}
	else {
		update(2*p+1,ind,val);
		update(2*p+2,ind,val);
		//這一步很重要，一定不能少
		tree[p].val = tree[2*p+1].val + tree[2*p+2].val;
	}
}

3.區間修改（帶pushdown()）

區間修改就是某一個區間的值都要進行修改，可能是將某一個區間的所有值都加一操作，如果把每一個參與進去的祖先和子孫節點都進行修改，會超時，這個時候線可以只改動祖先而子節點在要用到的時候再進行修改，用一個lazy標記（延遲標記），在要用到的時候再使用標記進行操作，

//區間修改,此處是將[L,R]所有元素全部加一 
void change(int p,int L,int R) {
	if(R < tree[p].l||L > tree[p].r ) 
		return;
	if(L <= tree[p].l && tree[p].r <= R) {
		//完全包含其中，直接改變標記并處理然后回傳即可 
		tree[p].val += (tree[p].r - tree[p].l +1);
		tree[p].lazy += 1;
		return;
	}
	//處理延遲標記，因為要用到左右兒子節點了 
	pushdown(p);
	int mid = (tree[p].l + tree[p].r)/2;
	if(L <= mid)	change(2*p+1,L,R);
	if(R >  mid) 	change(2*p+2,L,R);
	tree[p].val = tree[2*p+1].val + tree[2*p+2].val;
}

接下來介紹pushdown（）函式，這個函式的作用就是處理延遲標記，對于被標記了的節點，即lazy不為0,則先把標記傳遞給左右兒子，然后處理左右兒子的內容，最后再將這個標記清零，因為已經處理完成，

void pushdown(int p) {
	if(tree[p].lazy != 0){
		tree[2*p+1].lazy += tree[p].lazy;
		tree[2*p+2].lazy += tree[p].lazy;
		int mid = (tree[p].l + tree[p].r)/2;
		tree[2*p+1].val += mid - tree[p].l + 1;
		tree[2*p+2].val += tree[p].r - mid;
		tree[p].lazy = 0;//父節點的標記清零 
	}
}

最后提一點因為區間修改用的是懶標記，這個時候的查詢已經不是上面那個查詢了，同樣是需要用到pushdown()函式的查詢函式，但函式大體并沒有發生改變，

//查詢 
int _query(int p,int L,int R) {
	//終止條件
	if(tree[p].l>R||tree[p].r<L)
		return 0;
		
	int sum = 0;
	pushdown(p);
	if(tree[p].l>=L&&R>=tree[p].r) {
		sum += tree[p].val;
	} 		
	else {	
		int mid  = (L+R)/2;
		sum += _query(2*p+1,L,R);
		sum += _query(2*p+2,L,R);
	}
	return sum;
}

三.特殊的線段樹

還有兩個比較特特殊的乘法線段樹和根號線段樹，等以后再補吧，，，