Segment tree

Fishing大约 3 分钟

以下是模板

警告

构建函数 build：

叶子节点赋值改用 =，避免初始值累加错误。

标记下传 pushdown：

子节点标记 tag 改为累加（+=），防止覆盖未处理的标记。

区间修改 change_qj：

递归调用修正为 change_qj，而非错误的 query_qj。
无条件调用 pushdown 确保子节点数据最新。
标记 tag 使用累加操作，支持多次更新。

#include<bits/stdc++.h>
#define maxn 1145144

using namespace std;

int n,m;
int x,y,val,op;
int arr[maxn];
struct node {
    int l,r,w,tag;
} tree[maxn*4];

int ls(int k) {return k<<1;}
int rs(int k) {return k<<1|1;}
void build(int l,int r,int k) {
    tree[k].l=l;
    tree[k].r=r;
    
    if (l==r) {
        tree[k].w=arr[l];
        //cout<<tree[k].l<<" "<<tree[k].r<<" "<<tree[k].w<<endl;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(k));
    build(mid+1,r,rs(k));
    tree[k].w=tree[ls(k)].w+tree[rs(k)].w;
    //cout<<tree[k].l<<" "<<tree[k].r<<" "<<tree[k].w<<endl;
}
void pushdown(int k) {
    int lql=tree[ls(k)].l,lqr=tree[ls(k)].r;
    tree[ls(k)].w+=(lqr-lql+1)*tree[k].tag;
    tree[ls(k)].tag+=tree[k].tag;

    int rql=tree[rs(k)].l,rqr=tree[rs(k)].r;
    tree[rs(k)].w+=(rqr-rql+1)*tree[k].tag;
    tree[rs(k)].tag+=tree[k].tag;

    tree[k].tag=0;
}
void pushup(int k) {
    tree[k].w=tree[ls(k)].w+tree[rs(k)].w;
}
int query_qj(int k) {
    int l=tree[k].l;
    int r=tree[k].r;
    int mid=(l+r)>>1;
    int tot=0;
    if (l>=x && r<=y) return tree[k].w;
    if (tree[k].tag!=0) pushdown(k);
    if (x<=mid) tot+=query_qj(ls(k));
    if (y>=mid+1) tot+=query_qj(rs(k));
    return tot;
}
void change_qj(int k) {
    int l=tree[k].l;
    int r=tree[k].r;
    int mid=(l+r)>>1;
    if (tree[k].tag!=0) pushdown(k);
    if (l>=x && r<=y) {
        tree[k].w+=val*(r-l+1);
        tree[k].tag=val;
        return;
    }
    if (x<=mid) change_qj(ls(k));
    if (y>=mid+1) change_qj(rs(k));
    pushup(k);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>arr[i];
    }
    build(1,n,1);
    while(m--) {
        cin>>op;
        if (op==1) {
            cin>>x>>y>>val;
            change_qj(1);
        } else {
            cin>>x>>y;
            cout<<query_qj(1)<<endl;
        }
    }
}

典型例题：洛谷 P2846 Light Switching G

代码

#include<bits/stdc++.h>
#define maxn 1145144

using namespace std;

int n,m;
int x,y,op;
int arr[maxn];
struct node {
    int l,r,w,tag;//w为有多少灯是开着的，tag为懒标记
} tree[maxn*4];

int ls(int k) {return k<<1;}
int rs(int k) {return k<<1|1;}
void build(int l,int r,int k) {
    tree[k].l=l;
    tree[k].r=r;
    
    if (l==r) {
        tree[k].w=0;//灯初始为关
        //cout<<tree[k].l<<" "<<tree[k].r<<" "<<tree[k].w<<endl;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(k));
    build(mid+1,r,rs(k));
    tree[k].w=tree[ls(k)].w+tree[rs(k)].w;
    //cout<<tree[k].l<<" "<<tree[k].r<<" "<<tree[k].w<<endl;
}
void pushdown(int k) {
    if (tree[k].tag==0) return;

    int lql=tree[ls(k)].l,lqr=tree[ls(k)].r;
    tree[ls(k)].w=(lqr-lql+1)-tree[ls(k)].w;
    tree[ls(k)].tag^=1;//开关灯

    int rql=tree[rs(k)].l,rqr=tree[rs(k)].r;
    tree[rs(k)].w=(rqr-rql+1)-tree[rs(k)].w;
    tree[rs(k)].tag^=1;//开关灯

    tree[k].tag=0;
}
void pushup(int k) {
    tree[k].w=tree[ls(k)].w+tree[rs(k)].w;
}
int query_qj(int k) {
    int l=tree[k].l;
    int r=tree[k].r;
    int mid=(l+r)>>1;
    int tot=0;
    if (l>=x && r<=y) return tree[k].w;
    pushdown(k);
    if (x<=mid) tot+=query_qj(ls(k));
    if (y>=mid+1) tot+=query_qj(rs(k));
    return tot;
}
void change_qj(int k) {
    int l=tree[k].l;
    int r=tree[k].r;
    int mid=(l+r)>>1;
    pushdown(k);
    if (l>=x && r<=y) {
        tree[k].w=(r-l+1)-tree[k].w;
        tree[k].tag^=1;//开关灯
        return;
    }
    if (x<=mid) change_qj(ls(k));
    if (y>=mid+1) change_qj(rs(k));
    pushup(k);
}
int main()
{
    cin>>n>>m;
    build(1,n,1);
    while(m--) {
        cin>>op>>x>>y;
        if (op==0) {
            change_qj(1);
        } else {
            cout<<query_qj(1)<<endl;
        }
    }
}