线段树模板1求条悬关
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复13
  • 已保存回复14
  • 发布时间2024/3/19 12:24
  • 上次更新2024/3/19 16:53:00
查看原帖
线段树模板1求条悬关
745358
ChenZQ楼主2024/3/19 12:24
#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[100010];
int seg[400010],tag[400010];
struct node
{
    int l,r;
};
node lr[400010];

void push(int u)
{
    seg[u*2]+=tag[u]*(lr[u*2].r-lr[u*2].l+1);
    seg[u*2+1]+=tag[u]*(lr[u*2+1].r-lr[u*2+1].l+1);
    tag[u*2]+=tag[u];tag[u*2+1]+=tag[u];
    tag[u]=0;
}
void build_tree(int l,int r,int u)
{
    lr[u].l=l,lr[u].r=r;
    if(l==r) 
    {
        seg[u]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(l,mid,u*2);build_tree(mid+1,r,u*2+1);
    seg[u]=seg[u*2]+seg[u*2+1];
}
int ask(int x,int y,int l,int r,int u)
{
    push(u);
    if(l>r) return 0;
    if(l>=x && r<=y) return seg[u];
    int mid=(l+r)>>1;
    int ans=0;
    if(mid>=x && l<=y) ans+=ask(x,y,l,mid,u*2);
    if(r>=x && mid+1<=y) ans+=ask(x,y,mid+1,r,u*2+1);
    return ans;
}
void add(int x,int y,int l,int r,int u,int z)
{
    push(u);
    if(l>r) return;
    if(l>=x && r<=y) 
    {
        tag[u]+=z;
        seg[u]+=(r-l+1)*z;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x && l<=y) add(x,y,l,mid,u*2,z);
    if(r>=x && mid+1<=y) add(x,y,mid+1,r,u*2+1,z);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build_tree(1,n,1);
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int op;
        int x,y,z;
        cin>>op;
        if(op==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",ask(x,y,1,n,1));
        }
        else
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,1,n,1,z);
        }
    }
}
2024/3/19 12:24
加载中...