https://blog.csdn.net/yyt330507870/article/details/70037135

綜述

線段樹的原理：將[1,n]分解成若干特定的子區(qū)間(數(shù)量不超過4n),然后，將每個區(qū)間[L,R]都分解為少量特定的子區(qū)間，通過對這些少量子區(qū)間的修改或者統(tǒng)計，來實現(xiàn)快速對[L,R]的修改或者統(tǒng)計。
作用：對編號連續(xù)的一些點的區(qū)間信息進行修改或者統(tǒng)計操作
主要操作：區(qū)間查詢、點更新、區(qū)間更新
時間復(fù)雜度：修改和統(tǒng)計的復(fù)雜度都是O(log(N))*

由原理可以看出線段樹維護的信息必須滿足區(qū)間加法
如：
數(shù)字之和——總數(shù)字之和 = 左區(qū)間數(shù)字之和 + 右區(qū)間數(shù)字之和
最大公因數(shù)(GCD)——總GCD = gcd( 左區(qū)間GCD , 右區(qū)間GCD );
最大值——總最大值=max(左區(qū)間最大值，右區(qū)間最大值)

線段樹原理的詳細分析及應(yīng)用可以參考一篇寫得特別好的博文：線段樹詳解
這篇博客完全可以作為學習線段樹的指南及訓練線段樹的參考。

模板

為了規(guī)范自己的寫法，所以就整理一下模板。
以下模板ans[]存的是區(qū)間和，若存其他符合區(qū)間加法的信息，需要相應(yīng)改代碼。

(0)定義

const int MAXN=50010;
int a[MAXN],ans[MAXN<<2],lazy[MAXN<<2];
//a[]為原序列信息，ans[]模擬線段樹維護區(qū)間和，lazy[]為懶惰標記

(2)建樹

void Build(int l,int r,int rt)
{
    if (l==r)
    {
        ans[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    PushUp(rt);
}

(3) 下推懶惰標記

void PushDown(int rt,int ln,int rn)//ln表示左子樹元素結(jié)點個數(shù)，rn表示右子樹結(jié)點個數(shù)
{
    if (lazy[rt])
    {
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        ans[rt<<1]+=lazy[rt]*ln;
        ans[rt<<1|1]+=lazy[rt]*rn;
        lazy[rt]=0;
    }
}

(4)點更新

void Add(int L,int C,int l,int r,int rt)
{
    if (l==r)
    {
        ans[rt]+=C;
        return;
    }
    int mid=(l+r)>>1;
    //PushDown(rt,mid-l+1,r-mid); 若既有點更新又有區(qū)間更新，需要這句話
    if (L<=mid)
        Add(L,C,l,mid,rt<<1);
    else
        Add(L,C,mid+1,r,rt<<1|1);
    PushUp(rt);
}

(5)區(qū)間更新

void Update(int L,int R,int C,int l,int r,int rt)
{
    if (L<=l&&r<=R)
    {
        ans[rt]+=C*(r-l+1);
        lazy[rt]+=C;
        return;
    }
    int mid=(l+r)>>1;
    PushDown(rt,mid-l+1,r-mid);
    if (L<=mid) Update(L,R,C,l,mid,rt<<1);
    if (R>mid) Update(L,R,C,mid+1,r,rt<<1|1);
    PushUp(rt);
}

(6)區(qū)間查詢

LL Query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
        return ans[rt];
    int mid=(l+r)>>1;
    PushDown(rt,mid-l+1,r-mid);//若更新只有點更新，不需要這句
    LL ANS=0;
    if (L<=mid) ANS+=Query(L,R,l,mid,rt<<1);
    if (R>mid) ANS+=Query(L,R,mid+1,r,rt<<1|1);
    return ANS;
}

(7)調(diào)用函數(shù)

    //建樹   
    Build(1,n,1);   
    //點更新  
    Add(L,C,1,n,1);  
    //區(qū)間修改   
    Update(L,R,C,1,n,1);  
    //區(qū)間查詢   
    int ANS=Query(L,R,1,n,1);  

注：若只涉及點更新的題，只需用(1)(2)(4)(6)
若只涉及區(qū)間更新的題，需用(1)(2)(3)(5)(6)
若為兩種更新都有，則在所有向子區(qū)間查詢或更新前，都需PushDown()