求调

P3372 【模板】线段树 1

yzc001 @ 2024-02-16 21:38:00

#include<bits/stdc++.h>
using namespace std;
struct shu {
    int l,r,z;
    long long g,m;
} a[400010];
long long b[100010];
void zhongshu(int i,int l,int r) {
    a[i].l=l;
    a[i].r=r;
    a[i].m=(l+r)/2;
    if(l!=r) {
        zhongshu(i*2,l,a[i].m);
        zhongshu(i*2+1,a[i].m+1,r);
        a[i].z=a[i*2].z+a[i*2+1].z;
    }else{
        a[i].z=b[l];
    } 
    //cout<<i<<" "<<l<<" "<<r<<" "<<a[i].z<<endl;
}
void xiugai(int i,int l,int r,int g) {
    //cout<<i<<" "<<l<<" "<<r<<" "<<g<<endl;
    if(l==a[i].l&&r==a[i].r){
        a[i].g+=g;
    }else if(l>a[i].m) {
        xiugai(i*2+1,l,r,g+a[i].g);
        a[i*2].g+a[i].g;
        a[i].g=0;
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else if(r<=a[i].m){
        xiugai(i*2,l,r,g+a[i].g);
        a[i*2+1].g+a[i].g;
        a[i].g=0;
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else{
        xiugai(i*2,l,a[i].m,g+a[i].g);
        xiugai(i*2+1,a[i].m+1,r,g+a[i].g);
        a[i].g=0;
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }
}
int qiuhe(int i,int l,int r) {
    int ans=0;
    if(l==a[i].l&&r==a[i].r){
        ans+=(a[i].z+a[i].g*(a[i].r-a[i].l+1));
    }else if(l>a[i].m) {
        ans+=qiuhe(i*2+1,l,r);
    }else if(r<=a[i].m){
        ans+=qiuhe(i*2,l,r);
    }else {
        ans+=qiuhe(i*2,l,a[i].m);
        ans+=qiuhe(i*2+1,a[i].m+1,r);
    }
    //cout<<i<<" "<<l<<" "<<r<<" "<<ans<<endl;
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,x,y,k,o;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>b[i];
    }
    zhongshu(1,1,n);
    while(m--){
        cin>>o;
        if(o==1){
            cin>>x>>y>>k;
            xiugai(1,x,y,k);
        }else{
            cin>>x>>y;
            cout<<qiuhe(1,x,y)<<endl;
        }
    }
}

by Gold14526 @ 2024-02-16 22:08:02

帮你改完了，但是还是建议更改写法，毕竟线段树很常用，这种码风写起来有些臃肿。

这是帮你改好的码，改过的地方都标注了：

#include<bits/stdc++.h>
using namespace std;
struct shu {
    int l,r;
    long long z;                            //modified
    long long g,m;
} a[400010];
long long b[100010];
void zhongshu(int i,int l,int r) {
    a[i].l=l;
    a[i].r=r;
    a[i].m=(l+r)/2;
    if(l!=r) {
        zhongshu(i*2,l,a[i].m);
        zhongshu(i*2+1,a[i].m+1,r);
        a[i].z=a[i*2].z+a[i*2+1].z;
    }else{
        a[i].z=b[l];
    } 
    //cout<<i<<" "<<l<<" "<<r<<" "<<a[i].z<<endl;
}
void xiugai(int i,int l,int r,int g) {
    //cout<<i<<" "<<l<<" "<<r<<" "<<g<<endl;
    if(l==a[i].l&&r==a[i].r){               //modified
        a[i].g+=g;
    }else if(l>a[i].m) {
        xiugai(i*2+1,l,r,g);                //modified
        a[i*2].g+=a[i].g;                   //modified
        a[i*2+1].g+=a[i].g;                 //modified
        a[i].g=0;
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else if(r<=a[i].m){
        xiugai(i*2,l,r,g);                  //modified
        a[i*2].g+=a[i].g;                   //modified
        a[i*2+1].g+=a[i].g;                 //modified
        a[i].g=0;
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else{
        xiugai(i*2,l,a[i].m,g);             //modified
        xiugai(i*2+1,a[i].m+1,r,g);         //modified
        a[i*2].g+=a[i].g;                   //modified
        a[i*2+1].g+=a[i].g;                 //modified
        a[i].g=0;
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }
}
long long qiuhe(int i,int l,int r) {        //modefied
    long long ans=0;                        //modified
    if(a[i].l!=a[i].r){                     //modified
        a[i*2].g+=a[i].g;                   //modified
        a[i*2+1].g+=a[i].g;                 //modified
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
        a[i].g=0;                           //modified
    }                                       //modified
    if(l==a[i].l&&r==a[i].r){
        ans+=(a[i].z+a[i].g*(a[i].r-a[i].l+1));
    }else if(l>a[i].m) {
        ans+=qiuhe(i*2+1,l,r);
    }else if(r<=a[i].m){
        ans+=qiuhe(i*2,l,r);
    }else {
        ans+=qiuhe(i*2,l,a[i].m);
        ans+=qiuhe(i*2+1,a[i].m+1,r);
    }
    //cout<<i<<" "<<l<<" "<<r<<" "<<ans<<endl;
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,x,y,k,o;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>b[i];
    }
    zhongshu(1,1,n);
    while(m--){
        cin>>o;
        if(o==1){
            cin>>x>>y>>k;
            xiugai(1,x,y,k);
        }else{
            cin>>x>>y;
            cout<<qiuhe(1,x,y)<<endl;
        }
    }
}

这里贴一下我自己的码，比较简明一点：

#include<bits/stdc++.h>
using namespace std;
int num;
short zf;
char ch;
int read()
{
    num=0;
    zf=1;
    ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')zf=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*zf;
}
int n,q,a[1000001];
struct tree{
    int l,r,len;
    long long add,sum;
}t[4000001];
void push_down(int p)
{
    if(t[p].len==1||t[p].add==0)return;
    t[p<<1].add+=t[p].add;
    t[p<<1|1].add+=t[p].add;
    t[p<<1].sum+=t[p].add*t[p<<1].len;
    t[p<<1|1].sum+=t[p].add*t[p<<1|1].len;
    t[p].add=0; 
}
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    t[p].len=r-l+1;
    if(l==r)
    {
        t[p].sum=a[l];
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void change(int p,int l,int r,int x)
{
    if(t[p].l>r||t[p].r<l)return;
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].add+=x;
        t[p].sum+=1ll*x*t[p].len;
        return;
    }
    push_down(p);
    change(p<<1,l,r,x);
    change(p<<1|1,l,r,x);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
long long ask(int p,int l,int r)
{
    if(t[p].l>r||t[p].r<l)
    {
        return 0;
    }
    if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
    push_down(p);
    return ask(p<<1,l,r)+ask(p<<1|1,l,r);
}
short op;
int l,r,x;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read();
    q=read();
    for(int i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    while(q--)
    {
        op=read();
        if(op==1)
        {
            l=read();
            r=read();
            x=read();
            change(1,l,r,x);
        }
        else
        {
            l=read();
            r=read();
            printf("%lld\n",ask(1,l,r));
        }
    }
    return 0;
}

by Whycmd @ 2024-02-16 22:13:43

@yzc001


#include<bits/stdc++.h>
using namespace std;
struct shu {
    int l,r,z;
    long long g,m;
} a[400010];
long long b[100010];
void zhongshu(int i,int l,int r) {
    a[i].l=l;
    a[i].r=r;
    a[i].m=(l+r)/2;
    if(l!=r) {
        zhongshu(i*2,l,a[i].m);
        zhongshu(i*2+1,a[i].m+1,r);
        a[i].z=a[i*2].z+a[i*2+1].z;
    }else{
        a[i].z=b[l];
    } 
    //cout<<i<<" "<<l<<" "<<r<<" "<<a[i].z<<endl;
}
void xiugai(int i,int l,int r,int g) {
    //cout<<i<<" "<<l<<" "<<r<<" "<<g<<endl;
    if(l==a[i].l&&r==a[i].r){
        a[i].g+=g;
        //a[i].z+=g*(r-l+1);
    }else if(l>a[i].m) {
        a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;
        a[i].g=0;
        xiugai(i*2+1,l,r,g);
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else if(r<=a[i].m){
        a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;
        a[i].g=0;
        xiugai(i*2,l,r,g);
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else{
        a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;
        a[i].g=0;
        xiugai(i*2,l,a[i].m,g);
        xiugai(i*2+1,a[i].m+1,r,g);
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }
}
int qiuhe(int i,int l,int r) {
    int ans=0;
    if(l==a[i].l&&r==a[i].r){
        ans+=(a[i].z+a[i].g*(a[i].r-a[i].l+1));
    }else if(l>a[i].m) {
        a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;
        a[i].g=0;
        ans+=qiuhe(i*2+1,l,r);
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else if(r<=a[i].m){
        a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;
        a[i].g=0;
        ans+=qiuhe(i*2,l,r);
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }else {
        a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;
        a[i].g=0;
        ans+=qiuhe(i*2,l,a[i].m);
        ans+=qiuhe(i*2+1,a[i].m+1,r);
        a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);
    }
    //cout<<i<<" "<<l<<" "<<r<<" "<<ans<<endl;
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,x,y,k,o;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>b[i];
    }
    zhongshu(1,1,n);
    while(m--){
        cin>>o;
        if(o==1){
            cin>>x>>y>>k;
            xiugai(1,x,y,k);
        }else{
            cin>>x>>y;
            cout<<qiuhe(1,x,y)<<endl;
        }
        /*for(int i=1;i<=10;i++)
        cout<<a[i].l<<'~'<<a[i].r<<",val:"<<a[i].z<<",tag:"<<a[i].g<<endl

        ;cout<<endl;*/
    }
}

这是改完的代码,由于大量的错误,我只能给你一些对于你的部分问题的注意事项:

不管你要搜索那一部分,下推一定要两个子树一起推.
下推(就是a[i*2].g+=a[i].g,a[i*2+1].g+=a[i].g;a[i].g=0;)要在修改/求和之前做,维护(就是a[i].z=a[i*2].z+a[i*2].g*(a[i*2].r-a[i*2].l+1)+a[i*2+1].z+a[i*2+1].g*(a[i*2+1].r-a[i*2+1].l+1);)要在修改/求和之后做.
无论做什么操作,不管是修改还是求和,进入子树前一定要下推,操作完成后一定要维护.
建议不要把结果存成a[i].z+a[i].g*(a[i].r-a[i].l+1)这样的形式,a[i].g应该仅作为标记,而非用来存值,应将a[i].z直接作为结果(见多数题解的做法),因为许多题可能有许多作用同a[i].g和a[i].z的变量出现,如果按照后一种方法写不容易乱,也让别人更容易帮你改代码.

线段树问题每次检查时可以每次进行操作后完整检查一遍线段树,代码大体如下:

for(int i=1;i<=10;i++)
    cout<<"["<<a[i].l<<'~'<<a[i].r<<"]"<<",val:"<<a[i].z<<",tag:"<<a[i].g<<endl
    ;cout<<endl;

by Whycmd @ 2024-02-16 22:17:33

@yzc001 改完后的程序你还是看@Gold14526 这位的代码比较好,他的标注了改动的地方,可能对你帮助更大.

注:这是我的线段树代码,同样可以参考


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc (pl*2)
#define rc (pl*2+1)
#define mid ((lef+rig)>>1)
int a[4000010],n,m;
struct Tree
{
    int po[4000010],tag[4000010];
    void push_down(int pl,int lef,int rig)
    {
        po[lc] += tag[pl] * (mid-lef+1) , tag[lc] += tag[pl];
        po[rc] += tag[pl] * ( rig-mid ) , tag[rc] += tag[pl];
        tag[pl] = 0;
    }
    void clear(){memset(po,0,sizeof po),memset(tag,0,sizeof tag);   }
    void build(int pl,int lef,int rig)
    {
        if( lef == rig )    po[pl] = a[lef] ;
        else build( lc , lef , mid ) , build( rc , mid + 1 , rig ) ,
        po[pl] = po[lc] + po[rc]; 
    }
    void change(int pl,int lef,int rig,int flef,int frig,int val)
    {
        if( lef >= flef && rig <= frig )
        {
            tag[pl] += val,po[pl] += val * (rig-lef+1) ;
            return ;
        }
        push_down(pl,lef,rig);
        if( flef <= mid )   change( lc , lef , mid , flef , frig , val );
        if( frig >  mid )   change( rc ,mid+1, rig , flef , frig , val );
        po[pl] = po[lc] + po[rc];
    }
    int query(int pl,int lef,int rig,int flef,int frig)
    {
        int ans = 0;
        if( lef >= flef && rig <= frig )
        {
            return po[pl];
        }
        push_down( pl , lef , rig );
        if( flef <= mid )   ans += query( lc , lef , mid , flef , frig );
        if( frig >  mid )   ans += query( rc ,mid+1, rig , flef , frig );
        return ans;
    }
}tree;
signed main()
{
    scanf("%d%d",&n,&m);
    for( int i = 1; i <= n; ++ i )
    {
        scanf("%d",&a[i]);
    }
    tree.build(1,1,n);
    while( m -- )
    {
        int op,x,y,val;
        scanf("%d",&op);
        if( op == 1 )
        {
            scanf("%d%d%d",&x,&y,&val);
            tree.change(1,1,n,x,y,val);
        }
        if( op == 2 )
        {
            scanf("%d%d",&x,&y);
            cout<<tree.query(1,1,n,x,y)<<'\n';
        }
    }
}