資料結構：線段樹基礎詳解

1.簡介

線段樹，顧名思義，就是由線段構成的樹，是一個較為優秀的資料結構，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點，通常用於解決區間類的問題，在各大OI賽事中頻繁出現。下面我將為你展示線段樹的一些基本操作及原理

2.儲存

線段樹一般用結構體儲存，程式碼如下：

struct node{
    int l,r,num,add;
}tree[10010];
//add 用於懶標記

3.建樹

程式碼如下：

void buildtree(int x,int y,int p){
    t[p].l = x,t[p].r = y;
    if (x == y){
        t[p].sum = a[x];
        return;
    }
    int mid = x+y>>1;
    buildtree(x,mid,p<<1);
    buildtree(mid+1,y,(p<<1)+1);
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum;
}

4.懶標記

~~從前有一個人，太懶了，修改線段樹區間值時不想把線段樹全都遍歷一遍，於是就有了懶標記~~

懶標記的精髓就是打標記和下傳操作，由於我們要做的操作是區間加一個數，所以我們不妨在區間進行修改時為該區間打上一個標記，就不必再修改他的兒子所維護區間，等到要使用該節點的兒子節點維護的值時，再將懶標記下放即可，可以節省很多時間，對於每次區間修改和查詢，將懶標記下傳，可以節省很多時間。當然，這一操作不是必要的，在不住求程式碼執行速度的時候可以不用

程式碼如下：

void tag(int p){
    if (t[p].add){ //如果懶標記不為空，則進行下傳操作 
        t[p<<1].sum += t[p].add*(t[p<<1].r-t[p<<1].l+1); //這裡，因為luogu的模板題中修改是對於區間內每一個值的所以是乘
        t[(p<<1)+1].sum += t[p].add*(t[(p<<1)+1].r-t[(p<<1)+1].l+1);
        t[p<<1].add += t[p].add;
        t[(p<<1)+1].add += t[p].add;
        t[p].add = 0;
    }
}

5.區間修改

從根節點自上而下查詢，當發現有區間覆蓋要修改的節點時，我們就把這一區間修改並打上懶標記。否則下傳懶標記，繼續查詢。

程式碼如下：

void change(int p,int x,int y,int z){
    if (x<=t[p].l&&y>=t[p].r){
        t[p].sum+=(ll)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    if (x<=mid){
        change(p<<1,x,y,z);
    } //左兒子包含於修改區間內 
    if (y>mid){ //用if 不用else if 
        change((p<<1)+1,x,y,z);
    } //右兒子包含於修改區間內
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum; 
}

6.區間查詢

考慮詢問一個區間的和，依舊是從根節點向下查詢，當發現該節點被覆蓋時，就返回維護的值，否則下傳懶標記，查詢左右兒子，累加答案

程式碼如下：

long long ask(int p,int x,int y){
    if (x<=t[p].l&&y>=t[p].r){
        return t[p].sum;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    long long ans = 0;
    if (x<=mid) ans+=ask(p<<1,x,y);
    if (y>mid) ans+=ask((p<<1)+1,x,y);
    return ans;
}

7.完整程式碼

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[101010];
struct node{
    ll l,r,sum,add;
}t[401010];
void buildtree(int x,int y,int p){
    t[p].l = x,t[p].r = y;
    if (x == y){
        t[p].sum = a[x];
        return;
    }
    int mid = x+y>>1;
    buildtree(x,mid,p<<1);
    buildtree(mid+1,y,(p<<1)+1);
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum;
}
void tag(int p){
    if (t[p].add){ //如果懶標記不為空，則進行下傳操作 
        t[p<<1].sum += t[p].add*(t[p<<1].r-t[p<<1].l+1);
        t[(p<<1)+1].sum += t[p].add*(t[(p<<1)+1].r-t[(p<<1)+1].l+1);
        t[p<<1].add += t[p].add;
        t[(p<<1)+1].add += t[p].add;
        t[p].add = 0;
    }
}
void change(int p,int x,int y,int z){
    if (x<=t[p].l&&y>=t[p].r){
        t[p].sum+=(ll)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    if (x<=mid){
        change(p<<1,x,y,z);
    } //左兒子包含於修改區間內 
    if (y>mid){ //用if 不用else if 
        change((p<<1)+1,x,y,z);
    } //右兒子包含於修改區間內
    t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum; 
}
ll ask(int p,int x,int y){
    if (x<=t[p].l&&y>=t[p].r){
        return t[p].sum;
    }
    tag(p);
    int mid = t[p].l+t[p].r>>1;
    ll ans = 0;
    if (x<=mid) ans+=ask(p<<1,x,y);
    if (y>mid) ans+=ask((p<<1)+1,x,y);
    return ans;
}
int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    buildtree(1,n,1);
    int k,c,s,p;
    for (int i=1;i<=m;i++){
        cin>>k;
        if (k == 1){
            cin>>c>>s>>p;
            change(1,c,s,p);
        }
        else if (k == 2){
            cin>>c>>s;
            cout<<ask(1,c,s)<<endl;
        }
    }
    return 0;
}

Over~