關於線段樹基礎 - tw511教學網

首先明白什麼是線段樹：

線段樹是一棵二元樹，每個節點表示序列上的一段區間，其中根節點表示區間[1,n]
從根節點開始，只要區間長度不為1，就將區間劃分為兩半，並分給兩個子結點

如下圖，就是n=8的線段樹：

當節點表示區間[l,r]，當l≠r時，左孩子表示[l,(l+r)/2]，右孩子表示[(l+r)/2+1,r]

當l=r時，該節點為葉子節點

線段樹的基本性質：

性質1.總節點數為2n-1

性質2.線段樹並不一定是一棵完全二元樹，最後一層可能為空，且空結點的個數可能能達到2n個，因此最好開一棵4n的陣列來避免LE

性質3.層數約為，即每個葉節點到根節點的距離約為個節點組合而成性質

性質4.任何區間都可以用不超過2個結點組成

線段樹工作原理：

我們先線上段樹的每個節點都儲存該區間的總和。假設起始都為0

對於操作1，令A[x]加上y，我們先從根節點出發，找到[x,x]，比如x=3

此時，路徑上每個區間都包含x

接下來，將這些區間儲存的總和都加上y，比如y=4

這就是單點修改的工作原理，跟樹狀陣列有些相似之處，即修改一個點會對其祖先有同樣效果的影響，即要將其所有的祖先結點都通過修改的方式加上同樣的效果來保證影響的後效性。

問題2：詢問區間[x,y]的總和

就是尋找這個區間包含的最長且完整的、沒有交集的若干區間。

下面是線段樹的模板：

程式碼如下：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 
  5 #define ll long long
  6 
  7 inline int get()//快讀 
  8 {
  9     char c;
 10     int sign=1;
 11     while((c=getchar())<'0'||c>'9')
 12     {
 13         if(c=='-')
 14         {
 15             sign=-1;
 16         }
 17     }
 18     int res=c-'0';
 19     while((c=getchar())>='0'&&c<='9')
 20     {
 21         res=res*10+c-'0';
 22     }
 23     return res*sign;
 24 }
 25 
 26 const int N=1e5+5;
 27 int n,m,a[N];
 28 int add[N*4];
 29 ll sum[N*4];
 30 
 31 void build(int k,int l,int r)//建樹 
 32 {
 33     if(l==r)//區間長度為1，是葉節點，給它賦值 
 34     {
 35         sum[k]=a[l];
 36         return;
 37     }
 38     int mid=l+r>>1;
 39     build(k<<1,l,mid);//建他的左兒子 
 40     build(k<<1|1,mid+1,r);//建他的右兒子 
 41     sum[k]=sum[k<<1]+sum[k<<1|1];//他的區間和等於他兩個兒子的和 
 42 }
 43 
 44 int Add(int k,int l,int r,int v)//區間加並更新值 
 45 {
 46     add[k]+=v;//給懶標記更新值 
 47     sum[k]+=(ll)v*(r-l+1);//給區間和更新值 
 48 }
 49 
 50 void pushdown(int k,int l,int r,int mid)//進行懶標記的下放 
 51 {
 52     if(add[k]==0)
 53     {
 54         return ;//如果懶標記是0就直接跳過，不用在乎他 
 55     }
 56     Add(k<<1,l,mid,add[k]);//懶標記讓他的兩個兒子更新值 
 57     Add(k<<1|1,mid+1,r,add[k]);
 58     add[k]=0;//最後要將懶標記賦值0，以便下次懶標記更新值時不會受到上一次標記的影響 
 59 }
 60 
 61 ll query(int k,int l,int r,int x,int y)//詢問區間和，其中l和r代表的是當前存取的區間端點，x和y代表的是想要求和的區間端點 
 62 {
 63     if(l>=x&&r<=y) return sum[k];//如果當前存取的區間在求和區間以內，就將它的值返回給res 
 64     int mid=l+r>>1;
 65     ll res=0;
 66     pushdown(k,l,r,mid);//先進行標記下放，確保當前存取的區間是最新的 
 67     if(x<=mid) res+=query(k<<1,l,mid,x,y); 
 68     if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
 69     return res;
 70 }
 71 
 72 int modify(int k,int l,int r,int x,int y,int v)//給區間的每個元素加值得操作 
 73 {
 74     if(l>=x&&r<=y) return Add(k,l,r,v);//就是給它這個區間做標記 
 75     int mid=l+r>>1;
 76     pushdown(k,l,r,mid);
 77     if(x<=mid) modify(k<<1,l,mid,x,y,v);
 78     if(y>mid) modify(k<<1|1,mid+1,r,x,y,v);
 79     sum[k]=sum[k<<1]+sum[k<<1|1];
 80 }
 81 
 82 int main()
 83 {
 84     n=get(),m=get();
 85     for(int i=1;i<=n;++i)
 86     {
 87         a[i]=get();
 88     }
 89     build(1,1,n);
 90     ll a1,b,c,d,e,f;
 91     while(m--)
 92     {
 93         scanf("%lld",&a1);
 94         switch(a1)
 95         {
 96             case 1:{
 97                 scanf("%lld%lld%lld",&b,&c,&d);
 98                 modify(1,1,n,b,c,d);
 99                 break;
100             }
101             case 2:{
102                 scanf("%lld%lld",&e,&f);
103                 printf("%lld\n",query(1,1,n,e,f));
104                 break;
105             }
106         }
107     }
108     return 0;
109 }

以上就是線段樹的基本操作了，上面程式碼會存疑的地方大多都有註釋，最後只解釋有關懶標記的操作：

在沒有懶標記的時候，之前修改的位置都要立即更新，所以無形之中複雜度就高了很多，刺死就突出了懶標記的作用：

懶標記，顧名思義就是很懶的標記，每當我進行區間加的操作時，它起到了一個給目標區間記錄的作用，即區間不會立即修改，而是將每次的操作記錄並累計下來，只有當存取的元素包括此元素的時候才會將此元素依照對應的懶標記進行單點修改，也就從原來的直接降成，複雜度降了很多誒！

那好吧，由於本人能力有限，目前還無法解決關於區間乘除的問題，敬請期待！