目录

单点更新，区间最小值

#include 
    
     using namespace std;#define INF 0x3f3f3f3f#define TREE_SIZE (1<<(20))//#define localclass IntervalTree{    private:            // Top 重要        int Top[TREE_SIZE];        int size;        int _Query(int a,int b,int l,int r,int Ind)        {            if(a<=l&& b>=r)return  Top[Ind];            int mid=(l+r)>>1,ret=INF;            if(a<=mid) ret=min(ret,_Query(a,b,l,mid,Ind<<1));            if(b>mid) ret=min(ret,_Query(a,b,mid+1,r,(Ind<<1)+1));            return ret;                 }        void _Modify(int a,int l,int r,int Ind,int d)        {            if(l==r && l==a)            {                Top[Ind]=d;                             return ;            }            int mid=(l+r)>>1;            if(a<=mid) _Modify(a,l,mid,Ind<<1,d);            else _Modify(a,mid+1,r,(Ind<<1)+1,d);            Top[Ind]=min(Top[Ind<<1],Top[(Ind<<1)+1]);        }        public:            IntervalTree()            {                //memset(Cover,INF,sizeof(Cover));                memset(Top,INF,sizeof(Top));                size=(TREE_SIZE>>2)-1;            }            IntervalTree(int size):size(size)            {                //memset(Cover,INF,sizeof(Cover));                memset(Top,INF,sizeof(Top));            }            int Query(int a,int b)            {                return _Query(a,b,1,size,1);            }            void Modify(int a,int d)            {                return _Modify(a,1,size,1,d);            }}it;int main(){    #ifdef LOCAL    freopen("a.txt", "r", stdin);    #endif    //IntervalTree (*it)=new IntervalTree(7);    (it).Modify(1,2);       (it).Modify(2,8);    (it).Modify(3,4);    (it).Modify(4,1);    (it).Modify(5,6);    (it).Modify(6,7);    (it).Modify(7,3);        cout<<(it).Query(5,6)<
    

单点更新，区间最大值

#include 
    
     using namespace std;#define INF 0x3f3f3f3f#define TREE_SIZE (1<<(20))//#define localclass IntervalTree{    private:            // Top 重要        int Top[TREE_SIZE];        int size;        int _Query(int a,int b,int l,int r,int Ind)        {            if(a<=l&& b>=r)return  Top[Ind];            int mid=(l+r)>>1,ret=0;            if(a<=mid) ret=max(ret,_Query(a,b,l,mid,Ind<<1));            if(b>mid) ret=max(ret,_Query(a,b,mid+1,r,(Ind<<1)+1));            return ret;                 }        void _Modify(int a,int l,int r,int Ind,int d)        {            if(l==r && l==a)            {                Top[Ind]=d;                             return ;            }            int mid=(l+r)>>1;            if(a<=mid) _Modify(a,l,mid,Ind<<1,d);            else _Modify(a,mid+1,r,(Ind<<1)+1,d);            Top[Ind]=max(Top[Ind<<1],Top[(Ind<<1)+1]);        }        public:            IntervalTree()            {                //memset(Cover,0,sizeof(Cover));                memset(Top,0,sizeof(Top));                size=(TREE_SIZE>>2)-1;            }            IntervalTree(int size):size(size)            {                //memset(Cover,0,sizeof(Cover));                memset(Top,0,sizeof(Top));            }            int Query(int a,int b)            {                return _Query(a,b,1,size,1);            }            void Modify(int a,int d)            {                return _Modify(a,1,size,1,d);            }}it;int main(){    #ifdef LOCAL    freopen("a.txt", "r", stdin);    #endif    //IntervalTree (*it)=new IntervalTree(7);    (it).Modify(1,2);       (it).Modify(2,8);    (it).Modify(3,4);    (it).Modify(4,1);    (it).Modify(5,6);    (it).Modify(6,7);    (it).Modify(7,3);        cout<<(it).Query(5,6)<
    

单点更新，区间求和

#include 
    
     using namespace std;#define INF 0x3f3f3f3f#define TREE_SIZE (1<<(20))//#define localclass IntervalTree{    private:            // Top 重要        int Top[TREE_SIZE];        int size;        int _Query(int a,int b,int l,int r,int Ind)        {            if(a<=l&& b>=r)return  Top[Ind];            int mid=(l+r)>>1,ret=0;            if(a<=mid) ret+=_Query(a,b,l,mid,Ind<<1);            if(b>mid) ret+=_Query(a,b,mid+1,r,(Ind<<1)+1);            return ret;                 }        void _Modify(int a,int l,int r,int Ind,int d)        {            if(l==r && l==a)            {                Top[Ind]=d;                             return ;            }            int mid=(l+r)>>1;            if(a<=mid) _Modify(a,l,mid,Ind<<1,d);            else _Modify(a,mid+1,r,(Ind<<1)+1,d);            Top[Ind]=Top[Ind<<1]+Top[(Ind<<1)+1];        }        public:            IntervalTree()            {                //memset(Cover,0,sizeof(Cover));                memset(Top,0,sizeof(Top));                size=(TREE_SIZE>>2)-1;            }            IntervalTree(int size):size(size)            {                //memset(Cover,0,sizeof(Cover));                memset(Top,0,sizeof(Top));            }            int Query(int a,int b)            {                return _Query(a,b,1,size,1);            }            void Modify(int a,int d)            {                return _Modify(a,1,size,1,d);            }}it;int main(){    #ifdef LOCAL    freopen("a.txt", "r", stdin);    #endif    //IntervalTree (*it)=new IntervalTree(7);    (it).Modify(1,2);       (it).Modify(2,8);    (it).Modify(3,4);    (it).Modify(4,1);    (it).Modify(5,6);    (it).Modify(6,7);    (it).Modify(7,3);        cout<<(it).Query(5,6)<
    

区间替换，区间求和

#include
    
     #include
     
      #include
      
       using namespace std;const int MAX=1008600;int sum[MAX<<2],flag[MAX<<2];inline void PushUp(int idx){    sum[idx]=sum[idx<<1]+sum[idx<<1|1];}void Build(int idx,int left,int right){    // flag : -1表示没有懒惰标记    flag[idx]=-1;    if(left==right)    {        scanf("%d",sum+idx);        return ;    }    int mid=(left+right)>>1;    Build(idx<<1,left,mid);    Build(idx<<1|1,mid+1,right);    PushUp(idx);}// 懒惰标记的‘下放操作’inline void PushDown(int idx,int left,int mid){    int L=idx<<1,R=L+1;    sum[L]=(mid-left+1)*flag[idx];    sum[R]=sum[idx]-sum[L];    flag[L]=flag[R]=flag[idx];    flag[idx]=-1;}int L,R,val;void Update(int idx,int left,int right){    if(L<=left && right<=R)    {        sum[idx]=(right-left+1)*val;        // 放置懒惰标记        flag[idx]=val;        return;    }    int mid=(left+right)>>1;    if(flag[idx]!=-1) PushDown(idx,left,mid);    if(L<=mid) Update(idx<<1,left,mid);    if(mid
       
        >1,ans=0;    if(flag[idx]!=-1) PushDown(idx,left,mid);    if(L<=mid) ans+=Query(idx<<1,left,mid);    if(mid
       
      
     
    

区间更新(加上一个数字)，区间求和

// 线段树_区间修改区间求和#include
    
     #include
     
      #include
      
       using namespace std;const int MAX=1008600;int sum[MAX<<2],flag[MAX<<2];inline void PushUp(int idx){    sum[idx]=sum[idx<<1]+sum[idx<<1|1];}void Build(int idx,int left,int right){    // flag : -1表示没有懒惰标记    flag[idx]=-1;    if(left==right)    {        scanf("%d",sum+idx); return ;    }    int mid=(left+right)>>1;    Build(idx<<1,left,mid);    Build(idx<<1|1,mid+1,right);    PushUp(idx);}// 懒惰标记的‘下放操作’inline void PushDown(int idx,int left,int mid){    int L=idx<<1,R=L+1;    sum[L]=(mid-left+1)*flag[idx];    sum[R]=sum[idx]-sum[L];    flag[L]=flag[R]=flag[idx];    flag[idx]=-1;}int L,R,val;void Update(int idx,int left,int right){    if(L<=left && right<=R){        sum[idx]+=(right-left+1)*val;        // 放置懒惰标记        flag[idx]+=val;        return;    }    int mid=(left+right)>>1;    if(flag[idx]!=-1) PushDown(idx,left,mid);    if(L<=mid) Update(idx<<1,left,mid);    if(mid
       
        >1,ans=0;    if(flag[idx]!=-1) PushDown(idx,left,mid);    if(L<=mid) ans+=Query(idx<<1,left,mid);    if(mid