線段樹
一.概念（構建）
線段樹是一種基于二分思想的完全二叉樹，用于維護一段資料或陣列，并且使得所有操作的時間復雜度盡量維持在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 區間）
查詢區間和線段樹節點區間相交的不同情況：
- 查詢區間完全包含線段樹節點區間------------直接回傳該節點tree[p].sum
- 查詢區間和線段樹節點左孩子有交集---------往下遞回query(2*p+1,L,R)
- 查詢區間和線段樹節點右孩子有交集---------往下遞回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;
}
三.特殊的線段樹
還有兩個比較特特殊的乘法線段樹和根號線段樹，等以后再補吧，，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/221072.html
標籤：其他
上一篇：DS--最長重復子串
下一篇：2020-位元組-前端-面試