簡介

線段樹是一種應用極其廣泛，使用范圍較廣并且非常知名的樹形數據結構，主要用于進行區間操作，如區間修改，區間查詢等。這種數據結構唯一的不足就是巨大的代碼量，因此處理一些較簡單的問題時建議用樹狀數組。

原理

其實線段樹的原理是比較簡單的。我們平常見到的樹都是沒有特殊含義的，而線段樹的每個點都表示一個區間。詳細來講，線段樹其實是一顆二叉樹，我們會把一個數組轉換成一顆這樣的樹并進行多種操作。這是一顆線段樹的大致樣子。

可以看見，父節點表示的區間是兩個子節點表示的區間拼出來的。但是如果不知道父節點或子節點是誰這顆樹維護不了，我們因此可以定義一個結點u，并設它的左兒子為u*2,右兒子為u*2+1。這樣子就不可能存在重復結點的情況。當然這樣會消耗大量空間，因此要用到優化，我們待會兒講。

可以看出來如果想表示區間中的一段只需把這些分散的區間組合起來。那我們應該怎么組合？我們假設查詢的區間為[l,r],如果我們檢測到一個區間被完全包含我們就返回它的值。否則，我們取該區間的中間，把這個區間割開。如果檢測到查詢區間有一部分在左邊的區間，我們去查左邊。查右邊同理。這樣，我們可以以logn的復雜度把序列多余的部分一點一點消掉，直到無法查詢為止。

舉個例子，我們現在要在上圖中查詢[1,3]的值。首先我們從結點1開始，這里沒有完全包含，我們把結點1的區間從中間切開，變為[0,3]和[4,7],可以看出[4,7]與查詢區間完全不包含，我們轉而搜索[0,3]。

因為[0,3]依舊不是完全包含，我們將它切開，這是[2,3]被確定為完全包含，我們記錄[2,3]的值，發現[0,1]里只有1包含，我們把它提出來，這樣我們就把[1,3]拆成了1和[2,3]。

這時我們就完成了區間查詢，但我們可能還需要進行區間修改。怎么做呢？我們只需讓每個結點多維護一個懶標記。這個東西非常重要，因為如果每次我們都要把所有修改區間的子區間修改一遍復雜度不如直接修改。我們發現我們如果已經像之前把修改區間拆開，它們下面的結點目前沒有必要改，我們完全可以等搜到子節點以后再改。這樣修改也變成了logn的。

具體怎么操作？我們假設進行加操作，每次我們把修改的區間的懶標記加上修改值，等到有需要訪問子節點的操作時，我們把子節點的和加上其區間長度乘懶標記的值，并把懶標記加給左右兒子，最后把自己的懶標記清空就可以了。

實現

建樹

struct tree{int l,r,sum,lazy;
}t[4*N];
void build(int u, int l, int r){t[u].l=l,t[u].r=r;if(l==r){t[u].sum=a[l];return;}int mid=(l+r)>>1;build(u*2,l,mid), build(u*2+1,mid+1,r);t[u].sum=t[u*2].sum+t[u*2+1].sum;
}

這里的u就是每個樹上結點的編號，l和r表示這個結點表示的區間。當l=r說明這個結點表示一個元素，直接賦值即可。在搜索完子節點我們更新父節點的和。

懶標記下傳

void pushdown(int u){if(t[u].lazy){t[u*2].sum+=t[u].lazy*(t[u*2].r-t[u*2].l+1);t[u*2+1].sum+=t[u].lazy*(t[u*2+1].r-t[u*2+1].l+1);t[u*2].lazy+=t[u].lazy, t[u*2+1].lazy+=t[u].lazy;t[u].lazy=0;		}
}

這里的lazy就是懶標記，這里我們把父節點的懶標記加給兩個子節點，同時維護原來就該加的值。

區間修改

void update(int u, int l, int r, int c){if(t[u].l>=l&&t[u].r<=r){t[u].sum+=c*(t[u].r-t[u].l+1);t[u].lazy+=c;return;}pushdown(u);int mid=(t[u].l+t[u].r)>>1;if(mid>=l) update(u*2,l,r,c);if(r>mid) update(u*2+1,l,r,c);t[u].sum=t[u*2].sum+t[u*2+1].sum;
}

這里的l,r,c都是區間加的參數，不會變，真正表示結點信息的是u。我們看上面的判斷表示如果這個結點表示的區間被完全包含我們就給它帶上懶標記，維護區間和。如果不完全包含我們就需要下傳懶標記讓每次查詢時獲得的都是正確的值。這里我們去中間值將區間拆開。r需要大于mid是因為第二個區間的左端點是mid+1,我們需要判斷一下，這里寫r>=mid+1也是可以的。

區間查詢

int find(int u, int l, int r){if(t[u].l>=l&&t[u].r<=r) return t[u].sum;pushdown(u);int ans=0, mid=(t[u].l+t[u].r)>>1;if(mid>=l) ans+=find(u*2,l,r);if(r>mid) ans+=find(u*2+1,l,r);return ans;
}

這里的l，r同樣是查詢區間的左右端點，不會改變。可以看到我們每次查詢兒子前都要下傳懶標記，這樣兒子的值才是對的。我們只需維護一個計數器一層一層把答案傳上來即可。

優化

假設一個序列特別長，有一千萬個元素。這個時候開4倍空間會爆炸。這時我們就要用到動態開點。我們怎么做？之前定義了u的左兒子是u*2,右兒子是u*2+1,但這樣可能浪費大量空間。我們因此取消這個定義，維護一個計數器，表示目前有多少點。我們存兩個變量表示一個結點的兒子，每次添加時我們讓這個變量變成計數器，然后計數器++。

這樣我們可以節省大量空間，但代碼也極度復雜，這里就不放了。推薦一下OIwiki的模版。

例題及完整代碼

區間加區間查模版

代碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N],op,x,y,k;
struct tree{int l,r,sum,lazy;
}t[4*N];
void build(int u, int l, int r){t[u].l=l,t[u].r=r;if(l==r){t[u].sum=a[l];return;}int mid=(l+r)>>1;build(u*2,l,mid), build(u*2+1,mid+1,r);t[u].sum=t[u*2].sum+t[u*2+1].sum;
}
void pushdown(int u){if(t[u].lazy){t[u*2].sum+=t[u].lazy*(t[u*2].r-t[u*2].l+1);t[u*2+1].sum+=t[u].lazy*(t[u*2+1].r-t[u*2+1].l+1);t[u*2].lazy+=t[u].lazy, t[u*2+1].lazy+=t[u].lazy;t[u].lazy=0;		}
}
void update(int u, int l, int r, int c){if(t[u].l>=l&&t[u].r<=r){t[u].sum+=c*(t[u].r-t[u].l+1);t[u].lazy+=c;return;}pushdown(u);int mid=(t[u].l+t[u].r)>>1;if(mid>=l) update(u*2,l,r,c);if(r>mid) update(u*2+1,l,r,c);t[u].sum=t[u*2].sum+t[u*2+1].sum;
}
int find(int u, int l, int r){if(t[u].l>=l&&t[u].r<=r) return t[u].sum;pushdown(u);int ans=0, mid=(t[u].l+t[u].r)>>1;if(mid>=l) ans+=find(u*2,l,r);if(r>mid) ans+=find(u*2+1,l,r);return ans;
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(m--){cin>>op;if(op==1){cin>>x>>y>>k;update(1,x,y,k);}else{cin>>x>>y;cout<<find(1,x,y)<<endl;}}return 0;
}

線段樹進階題目

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,q,mod,a[N],op,x,y,k;
struct tree{int l,r,sum,mul,add;
}t[4*N];
void build(int u, int l, int r){t[u].l=l,t[u].r=r,t[u].mul=1;if(l==r){t[u].sum=a[l]%mod;return;}int mid=(l+r)>>1;build(u*2,l,mid);build(u*2+1,mid+1,r);t[u].sum=t[u*2].sum+t[u*2+1].sum;t[u].sum%=mod;
}
void pushd(int u){if(t[u].mul!=1||t[u].add){int L=u*2,R=u*2+1;t[L].sum=(1ll*t[L].sum*t[u].mul+t[u].add*(t[L].r-t[L].l+1))%mod;t[R].sum=(1ll*t[R].sum*t[u].mul+t[u].add*(t[R].r-t[R].l+1))%mod;t[L].mul=(1ll*t[L].mul*t[u].mul)%mod;t[R].mul=(1ll*t[R].mul*t[u].mul)%mod;t[L].add=(1ll*t[L].add*t[u].mul+t[u].add)%mod;t[R].add=(1ll*t[R].add*t[u].mul+t[u].add)%mod;t[u].mul=1,t[u].add=0;}
}
void update1(int u, int l, int r, int k){if(t[u].l>=l&&t[u].r<=r){t[u].sum=(1ll*t[u].sum*k)%mod;t[u].mul=(1ll*t[u].mul*k)%mod;t[u].add=(1ll*t[u].add*k)%mod;return;}pushd(u);int mid=(t[u].l+t[u].r)>>1;if(l<=mid) update1(u*2,l,r,k);if(r>mid) update1(u*2+1,l,r,k);t[u].sum=(t[u*2].sum+t[u*2+1].sum)%mod;
}
void update2(int u, int l, int r, int k){if(t[u].l>=l&&t[u].r<=r){t[u].sum=(t[u].sum+1ll*k*(t[u].r-t[u].l+1))%mod;t[u].add=(t[u].add+k)%mod;return;}pushd(u);int mid=(t[u].l+t[u].r)>>1;if(l<=mid) update2(u*2,l,r,k);if(r>mid) update2(u*2+1,l,r,k);t[u].sum=(t[u*2].sum+t[u*2+1].sum)%mod;
}
int find(int u, int l, int r){if(t[u].l>=l&&t[u].r<=r) return t[u].sum;pushd(u);int mid=(t[u].l+t[u].r)>>1,ans=0;if(l<=mid) ans+=find(u*2,l,r);if(r>mid) ans+=find(u*2+1,l,r);return ans;
}
signed main(){cin>>n>>q>>mod;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while(q--){cin>>op;if(op==1){cin>>x>>y>>k;update1(1,x,y,k);}else if(op==2){cin>>x>>y>>k;update2(1,x,y,k);}else{cin>>x>>y;cout<<find(1,x,y)%mod<<endl;}}return 0;
}

這里再給大家推薦幾個題單。

適合入門的題單

適合進階的題單