線段樹

線段樹基本概念

概述

線段樹，類似區(qū)間樹，是一個完全二叉樹，它在各個節(jié)點保存一條線段（數(shù)組中的一段子數(shù)組），主要用于高效解決連續(xù)區(qū)間的動態(tài)查詢問題，由于二叉結(jié)構(gòu)的特性，它基本能保持每個操作的復(fù)雜度為O(lgN)!
性質(zhì)：父親的區(qū)間是[a,b],(c=(a+b)/2)左兒子的區(qū)間是[a,c]，右兒子的區(qū)間是[c+1,b]，線段樹需要的空間為數(shù)組大小的四倍

基本操作（demo用的是查詢區(qū)間最小值）

線段樹的主要操作有：

1. 線段樹的構(gòu)造
   主要思想是遞歸構(gòu)造，如果當(dāng)前節(jié)點記錄的區(qū)間只有一個值，則直接賦值，否則遞歸構(gòu)造左右子樹，最后回溯的時候給當(dāng)前節(jié)點賦值

2. 區(qū)間查詢 query(int l,int r,int nl,int nr,int s)
   （其中s為當(dāng)前查詢節(jié)點，nl,nr為當(dāng)前節(jié)點存儲的區(qū)間，l,r為此次query所要查詢的區(qū)間）
   主要思想是把所要查詢的區(qū)間[a,b]劃分為線段樹上的節(jié)點，然后將這些節(jié)點代表的區(qū)間合并起來得到所需信息

3. 區(qū)間更新（線段樹中最有用的）
   需要用到延遲標(biāo)記，每個結(jié)點新增加一個標(biāo)記，記錄這個結(jié)點是否被進(jìn)行了某種修改操作(這種修改操作會影響其子結(jié)點)。對于任意區(qū)間的修改，我們先按照查詢的方式將其劃分成線段樹中的結(jié)點，然后修改這些結(jié)點的信息，并給這些結(jié)點標(biāo)上代表這種修改操作的標(biāo)記。在修改和查詢的時候，如果我們到了一個結(jié)點p，并且決定考慮其子結(jié)點，那么我們就要看看結(jié)點p有沒有標(biāo)記，如果有，就要按照標(biāo)記修改其子結(jié)點的信息，并且給子結(jié)點都標(biāo)上相同的標(biāo)記，同時消掉p的標(biāo)記。（優(yōu)點在于，不用將區(qū)間內(nèi)的所有值都暴力更新，大大提高效率，因此區(qū)間更新是最優(yōu)用的操作）

模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
long long sum[4000001],tag[4000001],a[4000001]; 
long long num;
int n,m;
inline int read(){
    int x=0,w=1;
    char ch=0;
    while(ch!='-'||(ch<'0'&&ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    whiel(ch>='0'&&ch=<'9') x+=x*10+ch-48,ch=getchar();
    return x*w;
}
void PushDown(int rt,int nl,int nr)
{
    if(tag[rt])
    {
        tag[rt<<1] += tag[rt];
        tag[rt<<1|1] += tag[rt];
        int mid=(nl+nr-1)>>1;
        sum[rt<<1] += tag[rt] * (mid-nl+1);
        sum[rt<<1|1] += tag[rt] * (nr-mid);
        tag[rt] = 0;//更新后需要還原
    }
}
void make(int l,int r,int nl,int nr,long long k,int s)
{
    if( nl==l&&nr==r){tag[s]+=k;sum[s]+=k*(nr-nl+1);return ;}
    if(nl==nr){return ;}
    PushDown(s,nl,nr);
    int mid=(nl+nr-1)>>1;
    if(r<=mid) make(l,r,nl,mid,k,s<<1);
    else if(l>mid) make(l,r,mid+1,nr,k,s<<1|1);
    else 
    {
        make(l,mid,nl,mid,k,s<<1);
        make(mid+1,r,mid+1,nr,k,s<<1|1);
    }
     sum[s]=sum[s<<1]+sum[s<<1|1];
}
void getup(int l,int r,int s)
{
    if(l==r){sum[s]=a[l];return ;}
    int mid=(l+r-1)/2;
    getup(l,mid,s<<1);
    getup(mid+1,r,s<<1|1);
    sum[s]=sum[s<<1]+sum[s<<1|1];
}
long long query(int l,int r,int nl,int nr,int s)
{
    if(nl==l&&nr==r)return num=sum[s];
    //if(nl==nr)return num=sum[s];
    PushDown(s,nl,nr);
    int mid=(nl+nr-1)>>1;
    if(r<=mid) return num=query(l,r,nl,mid,s<<1);
    else if(l>mid) return num=query(l,r,mid+1,nr,s<<1|1);
    else return num=query(l,mid,nl,mid,s<<1)+query(mid+1,r,mid+1,nr,s<<1|1);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        a[i]=read();
    getup(1,n,1);
    for(int i=1;i<=m;i++){
        int a;
        num=0;
        cin>>a;
        if(a==1){
            int x,y,k;
            x=read();
            y=read();
            k=read();
            make(x,y,1,n,k,1);
        }
        if(a==2){
            int x,y;
            x=read();
            y=read();
            cout<<query(x,y,1,n,1)<<endl;
        }
    }   
    return 0;
}