简介

线段树是一种可以用来维护区间信息常用的数据结构。线段树可以在线段树 - 图1的时间复杂度完成单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

查询时我们使用懒标记，当要用到时，再给他加上。

学当初学了一点，但是并没有完全掌握，现在重新学一下，毕竟比赛的时候就遇到了线段树的题目，结果一题都不会写。

主要是写的线段树的题目太少了，根本不可能做到灵活运用。

先上一个板子

  1. const int N=100010
  2. struct Node
  3. {
  4.     int l, r;
  5.     // TODO: 需要维护的信息和懒标记
  6. }tr[N * 4];
  8. void pushup(int u)
  9. {
  10.     // TODO: 利用左右儿子信息维护当前节点的信息
  11. }
  13. void pushdown(int u)
  14. {
  15.     // TODO: 将懒标记下传
  16. }
  18. void build(int u, int l, int r)
  19. {
  20.     if (l == r) tr[u] = {l, r};
  21.     else
  22.     {
  23.         tr[u] = {l, r};
  24.         int mid = l + r >> 1;
  25.         build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  26.         pushup(u);
  27.     }
  28. }
  30. void update(int u, int l, int r, int d)
  31. {
  32.     if (tr[u].l >= l && tr[u].r <= r)
  33.     {
  34.         // TODO: 修改区间
  35.     }
  36.     else
  37.     {
  38.         pushdown(u);
  39.         int mid = tr[u].l + tr[u].r >> 1;
  40.         if (l <= mid) update(u << 1, l, r, d);
  41.         if (r > mid) update(u << 1 | 1, l, r, d);
  42.         pushup(u);
  43.     }
  44. }
  46. int query(int u, int l, int r)
  47. {
  48.     if (tr[u].l >= l && tr[u].r <= r)
  49.     {
  50.         return ;  // TODO 需要补充返回值
  51.     }
  52.     else
  53.     {
  54.         pushdown(u);
  55.         int mid = tr[u].l + tr[u].r >> 1;
  56.         int res = 0;
  57.         if (l <= mid ) res = query(u << 1, l, r);
  58.         if (r > mid) res += query(u << 1 | 1, l, r);
  59.         return res;
  60.     }
  61. }

模板题

洛谷P3372

区间更新，区间查询，在一段区间加上一个数，查询一段区间的和。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=1000010;
  6. ll a[N],sum[N<<2],lazy[N<<4]; //树状数组长度最大不会超过4*n
  7. //构造线段树
  8. void build(int rt,int l,int r){
  9.     if(l==r){
  10.         sum[rt] = a[l];
  11.         lazy[rt] = 0;
  12.         return;
  13.     }//递归构造左右子树
  14.     int mid=l+r>>1;
  15.     build(rt<<1,l,mid);
  16.     build(rt<<1|1,mid+1,r);
  17.     sum[rt]=sum[rt<<1] + sum[rt<<1|1];//把父区间[l,r],分成左右两个[l,mid],(mid,r]区间。
  18. }
  19. //向下传递
  20. void push_down(int rt,int l,int r){
  21.     int mid=l+r>>1;
  22.     if(lazy[rt]){
  23.         sum[rt<<1]+=lazy[rt]*(mid-l+1);//维护区间和，如果是别的可以改
  24.         sum[rt<<1|1]+=lazy[rt]*(r-mid);
  25.         lazy[rt<<1]+=lazy[rt];
  26.         lazy[rt<<1|1]+=lazy[rt];//懒标记的值传递
  27.         lazy[rt]=0;
  28.     }
  29. }
  30. //更新值
  31. void update(int rt,int l,int r,int L,int R,int z){
  32.     int mid=l+r>>1;
  33.     if(L<=l&&r<=R){
  34.         sum[rt]+=z*(r-l+1);//维护区间和，如果是别的可以改
  35.         lazy[rt]+=z;
  36.         return;
  37.     }
  38.     push_down(rt,l,r);
  39.     if(L<=mid) update(rt<<1,l,mid,L,R,z);
  40.     if(R>mid) update(rt<<1|1,mid+1,r,L,R,z);
  41.     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
  42. }
  44. //查询值
  45. ll query(int rt,int l,int r,int L,int R){
  46.     int mid=l+r>>1;
  47.     if(L<=l&&r<=R){
  48.         return sum[rt];
  49.     }
  50.     push_down(rt,l,r);
  51.     ll res=0;
  52.     if(L<=mid) res+=query(rt<<1,l,mid,L,R);
  53.     if(R>mid) res+=query(rt<<1|1,mid+1,r,L,R);
  54.     return res;
  55. }
  57. int main(){
  58.     int n,m;
  59.     scanf("%d%d",&n,&m);
  60.     for(int i=1;i<=n;i++){
  61.         scanf("%lld",&a[i]);
  62.     }
  63.     build(1,1,n);
  64.     while(m--){
  65.         int op;
  66.         scanf("%d",&op);
  67.         if(op&1){
  68.             int x,y,z;
  69.             scanf("%d%d%d",&x,&y,&z);
  70.             update(1,1,n,x,y,z);
  71.         }
  72.         else{
  73.             int x,y;
  74.             scanf("%d%d",&x,&y);
  75.             printf("%lld\n",query(1,1,n,x,y));
  76.         }
  77.     }
  78.     return 0;
  79. }

P3373

区间乘上一个数，求一段区间的和

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long 
  4. const int N=100010;
  5. int mod;
  6. int sum[N<<2],mul[N<<2],lazy[N<<2],a[N];
  7. void push_up(int rt){
  8.     sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
  9. }
  11. void push_down(int rt,int l,int r){
  12.     int mid=l+r>>1;
  13.     if(mul[rt]!=1){
  14.         mul[rt<<1]=(mul[rt<<1]*mul[rt])%mod;
  15.         mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%mod;
  16.         lazy[rt<<1]=(lazy[rt<<1]*mul[rt])%mod;
  17.         lazy[rt<<1|1]=(lazy[rt<<1|1]*mul[rt])%mod;
  18.         sum[rt<<1]=(sum[rt<<1]*mul[rt])%mod;
  19.         sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt])%mod;
  20.         mul[rt]=1;
  21.     }
  22.     if(lazy[rt]){
  23.         sum[rt<<1]=(sum[rt<<1]+lazy[rt]*(mid-l+1))%mod;
  24.         sum[rt<<1|1]=(sum[rt<<1|1]+lazy[rt]*(r-mid))%mod;
  25.         lazy[rt<<1]=(lazy[rt<<1]+lazy[rt])%mod;
  26.         lazy[rt<<1|1]=(lazy[rt<<1|1]+lazy[rt])%mod;
  27.         lazy[rt]=0;
  28.     }
  29. }
  31. void build(int rt,int l,int r){
  32.     mul[rt]=1;
  33.     if(l==r){
  34.         sum[rt]=a[l];
  35.         return;
  36.     }
  37.     int mid=l+r>>1;
  38.     build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
  39.     push_up(rt);
  40. }
  42. void update1(int rt,int l,int r,int L,int R,int d){
  43.     if(L<=l && r<=R){
  44.         mul[rt]=mul[rt]*d%mod;
  45.         lazy[rt]=lazy[rt]*d%mod;
  46.         sum[rt]=sum[rt]*d%mod;
  47.         return;
  48.     }
  49.     push_down(rt,l,r);
  50.     int  mid=l+r>>1;
  51.     if(L<=mid) update1(rt<<1,l,mid,L,R,d);
  52.     if(R>mid) update1(rt<<1|1,mid+1,r,L,R,d);
  53.     push_up(rt);
  54. }
  56. void update2(int rt,int l,int r,int L,int R,int d){
  57.     if(L<=l && r<=R){
  58.         sum[rt]=(sum[rt]+d*(r-l+1))%mod;
  59.         lazy[rt]=(lazy[rt]+d)%mod;
  60.         return;
  61.     }
  62.     push_down(rt,l,r);
  63.     int mid=l+r>>1; 
  64.     if(L<=mid) update2(rt<<1,l,mid,L,R,d);
  65.     if(R>mid) update2(rt<<1|1,mid+1,r,L,R,d);
  66.     push_up(rt);
  67. }
  69. int query(int rt,int l,int r,int L,int R){
  70.     if(L<=l&& r<=R) return sum[rt];
  71.     push_down(rt,l,r);
  72.     int res=0;
  73.     int mid=l+r>>1;
  74.     if(L<=mid) res+=query(rt<<1,l,mid,L,R);
  75.     res%=mod;
  76.     if(R>mid) res+=query(rt<<1|1,mid+1,r,L,R);
  77.     return res%mod; 
  78. }
  80. signed main(){
  81.     int n,m,p;
  82.     cin>>n>>m>>mod;
  83.     for(int i=1;i<=n;i++){
  84.         cin>>a[i];
  85.     }
  86.     build(1,1,n);
  87.     while(m--){
  88.         int op,l,r,d;
  89.         cin>>op;
  90.         if(op==1){
  91.             cin>>l>>r>>d;
  92.             update1(1,1,n,l,r,d);
  93.         }
  94.         else if(op==2){
  95.             cin>>l>>r>>d;
  96.             update2(1,1,n,l,r,d);
  97.         }
  98.         else if(op==3){
  99.             cin>>l>>r;
  100.             cout<<query(1,1,n,l,r)<<endl;
  101.         }
  102.     }
  103.     return 0; 
  104. }

维护区间最小值

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N = 5e5 + 7;
const int M = 1e6 + 7;
const int mod = 1e9 + 7;
const double eps = 1e-6;
ll t, n, k,m;
int a[N],tree[N<<2];
void build(int rt,int l,int r){
    if(l==r){
        tree[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}

void update(int rt,int l,int r,int x,int y){
    if(l==r){
        tree[rt]=y;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        update(rt<<1,l,mid,x,y);
    }
    else{
        update(rt<<1|1,mid+1,r,x,y);
    }
    tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}

int query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return tree[rt];
    }
    int mid=(l+r)>>1;
    int ans=1e9+10;
    if(L<=mid) ans=min(ans,query(rt<<1,l,mid,L,R));
    if(R>mid) ans=min(ans,query(rt<<1|1,mid+1,r,L,R));
    return ans;
}

void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        int op,x,y;
        cin>>op;
        if(op==1){
            cin>>x>>y;
            update(1,1,n,x,y);
            a[x]=y;
        }
        else{
            cin>>x;
            int al,ar,l=1,r=x;
            while(l<r){
                //TODO
                int mid=(l+r)>>1;
                if(query(1,1,n,mid,x)>=a[x]) r=mid;
                else l=mid+1;
            }
              al=x-l+1;
              l=x,r=n+1;
              while(l<r){
                  int mid=(l+r)>>1;
                  if(query(1,1,n,x,mid)<a[x]) r=mid;
                  else l=mid+1;
            }
            l--;
            ar=l-x+1;
            cout<<1ll*al*ar<<endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    t=1;
    //cin >> t;
    while(t--) solve();
    return 0;
}

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
const int INF=0x3f3f3f3f;
int a[N],mn[N<<2],need[N<<2],he[N],res=1,h=0;

void update(int rt,int l,int r,int x,int val){
    if(l==r){
        mn[rt]=val;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) update(rt<<1,l,mid,x,val);
    if(x>mid) update(rt<<1|1,mid+1,r,x,val);
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}


int query(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y) return mn[rt];
    int mid=l+r>>1,ans=INF;
    if(x<=mid) ans=min(query(rt<<1,l,mid,x,y),ans);
    if(y>mid) ans=min(query(rt<<1|1,mid+1,r,x,y),ans);
    return ans;
}

int main(){
    int n,k;
    cin>>k>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        if(i<k){//前面k个，先初始化 
            update(1,0,k-1,i,x+y);
            he[i]++;
            continue;
        }
        if(mn[1]>x) continue;//如果当前所有都不能满足，直接跳过
        int d=i%k,l,r,ans;
        int tot=query(1,0,k-1,d,k-1);
        if(tot<=x){
            l=d,r=k-1;//i%k的后半段 
        } 
        else{//i%k的前半段 
            l=0,r=d-1; 
        }
        //二分查找区间长度，确定位置最靠近左边的合适的位置
        while(l<=r){
            int mid=l+r>>1;
            if(query(1,0,k-1,l,mid)<=x) ans=mid,r=mid-1;
            else l=mid+1;
        } 
        update(1,0,k-1,ans,x+y);
        he[ans]++;
        res=max(res,he[ans]);//记录处理最多事件的数量
        //printf("res = %d\n",res); 
    }
    for(int i=0;i<k;i++){
        //printf("%d ",he[i]);
        if(he[i]==res) need[++h]=i;
    }
    //puts("");
    for(int i=1;i<=h;i++){
        if(i!=1) printf(" ");
        printf("%d",need[i]);
    }
}