题解：P3368 【模板】树状数组 2

· · 题解

P3368 【模板】树状数组 2

看到题解里没有线段树的解法，所以我来水一发（雾）

题目理解：

本题要求实现两种对数列的操作：区间修改与单点查询，可以不假思索想到利用线段树来进行解决。相对于树状数组来说线段树所增加的部分常数复杂度对通过本题并没有影响。同时线段树的板子比较规整，实际码的时候也更不容易出问题。

剩下的主要来看代码理解吧，注释与部分注意事项写在注释里了

Code：

#include <bits/stdc++.h>
#define LL long long
#define endl '\n'
#define Aurora main
#define int LL
using namespace std;
const int N=1000001;
int segt[N],w[N*4],lzy[N*8];
int n,m,q;

void pushup(int u){//更新
    w[u]=w[u*2]+w[u*2+1];
}

void bt(int u,int l,int r){//建树
    if(l==r) {
        w[u]=segt[l];
        return;
    }
    int mid=(l+r)>>1;
    bt(u*2,l,mid);bt(u*2+1,mid+1,r);
    pushup(u);
}

void mtag(int u,int len,int x){//打懒标记
    lzy[u]+=x;
    w[u]+=len*x;
}

//懒标记是为了降低区间修改的复杂度,只有在节点被查询或修改访问到的时候才会对点进行更新并下放

void pushdown(int u,int l,int r){//节点标记下放
    int mid=(l+r)>>1;
    mtag(u*2,mid-l+1,lzy[u]);
    mtag(u*2+1,r-mid,lzy[u]);
    lzy[u]=0;
}

//单点操作
int que(int u,int l,int r,int p){//单点查询
    if(l==r) return w[u];
    else{
        int mid=(l+r)>>1;
        pushdown(u,l,r);//千万不要忘记加pushdown!!!
        if(mid>=p) return que(u*2,l,mid,p);
        else return que(u*2+1,mid+1,r,p);
    }
}

bool inr(int L,int R,int l,int r){//[l,r]被[L,R]包含
    return (l<=L)&&(r>=R);
}

bool outr(int l,int r,int L,int R){//[l,r]与[L,R]完全无交集
    return (L>r)||(R<l);
}

void rupd(int u,int L,int R,int l,int r,int x){//区间修改
    if(inr(L,R,l,r)) mtag(u,R-L+1,x);
    else if(!outr(L,R,l,r)){
        int mid=(L+R)/2;
        pushdown(u,L,R);
        rupd(u*2,L,mid,l,r,x);
        rupd(u*2+1,mid+1,R,l,r,x);//左右子树递归
        pushup(u);
    }
}

signed Aurora(){
    int a,b,c;
    scanf("%lld%lld",&n,&m);

    for(int i=1;i<=n;i++) scanf("%lld",&segt[i]);

    bt(1,1,n);//建立线段树

    int op;
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){//修改
            scanf("%lld%lld%lld",&a,&b,&c);
            rupd(1,1,n,a,b,c);
        }
        else{//查询
            scanf("%lld",&a);
            printf("%lld\n",que(1,1,n,a));
        }
    }
    return 0;
}

ps:对线段树不太理解的话可以来看线段树←这篇讲解，讲的真的很详细qwq

（讲解转自CSDN博客，违规自删）