線段樹（重新學習）

這已經是我第三次學習線段樹了

第一次學習線段樹，是懵逼狀态，第二次複習線段樹，小有了解，這次也不知道會怎麼樣，但是還是準備再學習一下線段樹，而且之前寫的線段樹講解很粗糙

為什麼要學習線段樹

比如​

​1---1e7​

​這個區間，我想知道這個區間的和，用for循環可以寫:

for(int i=1;i<=1e7;i++)
sum+=a[i];
注意:每一個點的值是随機的,1--1e7并不呈線性
這樣求解的效率十分的低,每當我想知道一個大區間的和的時候
就需要循環很多次,這樣O(n)的時間複雜度是無法滿足要求的      

線段樹的時間複雜度是​

​log(n)​

​,效率十分高

線段樹

線段樹可以說是一個二叉樹，基于二分的思想寫的，将大區間不斷分下去，最後一個大區間變成多個點，每一個節點代表它再分下去的兩個區間的（資訊所進行的操作,比如兩個節點相加）

接下來開始繪一個8個節點的線段樹圖:

在建圖的過程中我們可以得到上圖中包含的所有區間的資訊

舉個栗子：

我們要求圖上所有區間的和

1-->8區間的和:36
5-->8區間的和:26
7-->8區間的和:15
5-->6區間的和:11
1-->4區間的和:10
8-->8區間的和:8
3-->4區間的和:7
7-->7區間的和:7
6-->6區間的和:6
5-->5區間的和:5
4-->4區間的和:4
1-->2區間的和:3
3-->3區間的和:3
2-->2區間的和:2
1-->1區間的和:1      

如何建圖:

寫一個結構體,存儲節點的資訊
#define maxn 1005
struct settree
{
    int l,r;//區間端點
    int sum;//區間和
    
}tree_p[4*maxn+5];      

void update(int k)//區間維護,記錄節點資訊
{
    tree_p[k].sum=tree_p[k*2].sum+tree_p[k*2+1].sum;
    //目前節點的和為其左右子節點的和
}      

建圖：

void set_tree(int k,int l,int r)
{
    tree_p[k].l=l;//記錄該節點的區間
    tree_p[k].r=r;
    if(l==r)//當區間縮為點時，指派即可
    {
        tree_p[k].sum=w[l];
        return ;
    }
    int mid=(l+r)/2;
    set_tree(k*2,l,mid);//左子葉
    set_tree(k*2+1,mid+1,r);//右子葉
    update(k);//回溯的時候維護節點的資訊
}      

建完圖之後，就該詢問區間的資訊了，現在将區間查詢，我把這個圖再拿下來，再觀察一下有什麼問題

在建樹的時候我說了，圖中包含的區間 。呢麼圖中當然有一些區間并沒有包含。例如:[3,6]區間，[2,3]區間等。我們要知道這些區間的資訊，可以通過合并幾個區間去得到答案

int query_ans(int k,int l,int r)
{
    if(tree_p[k].l>=l&&tree_p[k].r<=r)//在區間内
    {
        return tree_p[k].sum;
    }
    int mid=(tree_p[k].l+tree_p[k].r)>>1;
    if(mid>=r)//說明我們要求的區間,在節點k的左區間
    {
        return query_ans(k*2,l,r);
    }
    if(mid<l)
    {
        return query_ans(k*2+1,l,r);//說明在節點k的右區間
    }
    return query_ans(k*2,l,r)+query_ans(k*2+1,l,r);
}      

接下來講單點修改，所謂牽一發而動全身，改一點而動全局，通過要修改的點​

​x​

​​，尋找x點，更改x點的值，然後回溯到節點​

​1​

​​，在回溯的過程中更改每一個節點的​

​sum​

​

void point_chan(int k,int x,int y)//單點修改
{
    if(tree_p[k].l==tree_p[k].r)
    {
        tree_p[k].sum=y;
        return ;
    }
    int mid=(tree_p[k].l+tree_p[k].r)>>1;
    if(mid>=x)//通過比較每一個節點的mid判斷x的在該節點的那一邊
    {
        point_chan(k*2,x,y);
    }
    else
    {
        point_chan(k*2+1,x,y);
    }
    update(k);
}      

區間修改和區間查詢

對于區間修改，我們如果按照單點一個一個修改，呢麼效率會很低，時間複雜度為​

​O(nlogn)​

​​,這裡引入懶人标記​

​lazy​

​​,來高效的進行​

​O(logn)​

​更高效的操作

void push_down(int k)//下傳懶人标記
{
    if(tree[k].l==tree[k].r)//如果沒有葉子節點就不下傳
    {
        tree[k].lazy=0;
        return;
    }
    if(tree[k].lazy)//開始下傳
    {
        tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].lazy;
        tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].lazy;
        tree[k<<1].lazy+=tree[k].lazy;
        tree[k<<1|1].lazy+=tree[k].lazy;
        tree[k].lazy=0;
    }
}      

void setment(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)//在回溯過程中完成操作
    {

        tree[k].sum+=(r-l+1)*x;
        tree[k].lazy+=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        setment(k<<1,l,r,x);
    }
    else if(mid<l)
    {
        setment(k<<1|1,l,r,x);
    }
    else
    {
        setment(k<<1,l,mid,x);
        setment(k<<1|1,mid+1,r,x);
    }
    push_up(k);
}      

int query_ans(int k,int l,int r)//修改區間和單點不一樣
{
    if(tree[k].lazy)
        push_down(k);
    if(tree[k].l>=l&&tree[k].r<=r)
    {
        return tree[k].sum;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        return query_ans(k<<1,l,r);
    }
    else if(l>mid)
    {
        return query_ans(k<<1|1,l,r);
    }
    return query_ans(k<<1,l,mid)+query_ans(k<<1|1,mid+1,r);
}      

完整的區間更改代碼：

#include<bits/stdc++.h>
using namespace std;
//線段樹區間更新,區間查詢
#define maxn 1005
struct node
{
    int sum,l,r,lazy;//區間求和
} tree[maxn];
int w[maxn];
void push_up(int k)//區間維護
{
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
}
void push_down(int k)//下傳懶人标記
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].lazy=0;
        return;
    }
    if(tree[k].lazy)
    {
        tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].lazy;
        tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].lazy;
        tree[k<<1].lazy+=tree[k].lazy;
        tree[k<<1|1].lazy+=tree[k].lazy;
        tree[k].lazy=0;
    }
}
void set_tree(int k,int l,int r)
{
    tree[k].l=l;
    tree[k].r=r;
    if(l==r)
    {
        tree[k].sum=w[l];
        return;
    }
    int mid=(l+r)>>1;
    set_tree(k<<1,l,mid);
    set_tree(k<<1|1,mid+1,r);
    push_up(k);//區間維護
}
void setment(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)//在回溯過程中完成操作
    {

        tree[k].sum+=(r-l+1)*x;
        tree[k].lazy+=x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        setment(k<<1,l,r,x);
    }
    else if(mid<l)
    {
        setment(k<<1|1,l,r,x);
    }
    else
    {
        setment(k<<1,l,mid,x);
        setment(k<<1|1,mid+1,r,x);
    }
    push_up(k);
}
int query_ans(int k,int l,int r)//修改區間和單點不一樣
{
    if(tree[k].lazy)
        push_down(k);
    if(tree[k].l>=l&&tree[k].r<=r)
    {
        return tree[k].sum;
    }
    int mid=(tree[k].l+tree[k].r)>>1;
    if(mid>=r)
    {
        return query_ans(k<<1,l,r);
    }
    else if(l>mid)
    {
        return query_ans(k<<1|1,l,r);
    }
    return query_ans(k<<1,l,mid)+query_ans(k<<1|1,mid+1,r);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    set_tree(1,1,n);
    int l,r,x;
    cin>>l>>r;
    int ans=query_ans(1,l,r);
    cout<<ans<<endl;
    cin>>l>>r>>x;
    setment(1,l,r,x);
    cout<<query_ans(1,l,r)<<endl;

}