题解 P3372 【【模板】线段树 1】

PM250 · 2017-08-25 08:51:17 · 题解

zkw(重口味)线段树，详见zkw的PPT

zkw线段树的操作是从下到上的，没有回溯，用循环代替。各种操作的思想同普通线段树。

1.开long long

2.lb-getlong(k) 子树中叶节点个数

3.左子树a[i<<1]，右子树a[i<<1|1]

4.a[]该节点子树的和，mark[]该节点被覆盖次数

5.zkw线段树只能查询(0,bit)，所以只有bit-2个叶节点，bit-2<n要扩大

附上代码

#include <iostream>
#include<cstdio>
#define ll long long
using namespace std;
int n,m;
ll a[400005],mark[400005];
ll bit,lb;
inline int getlong(int k)//查询结点第几层
{
    int i=0;
    while(k>>=1)i++;
    return i;
}
inline int put(int k,int t)//修改
{
    int tmp=1<<(lb-getlong(k));
    while(k>>=1)
        a[k]+=t*tmp;
    return 0;
}
inline ll get1(ll k)//查询
{
    ll tmp=1<<(lb-getlong(k));tmp有多少叶节点就加几倍
    ll re=a[k]+mark[k]*tmp;
    do
    {
        k>>=1;
        re+=mark[k]*tmp;
    }while(k);
    return re;
}
inline ll get(ll s,ll t)//区间查询
{
    ll re=0;
    for(s=s+bit-1,t=t+bit+1;s^t^1;s>>=1,t>>=1)//s-1和t+1变开区间，s+bit和t+bit到对应叶节点
    {
        if(!(s&1))
            re+=get1(s^1);//*(1<<(lb-getlong(s)));
        if(t&1)
            re+=get1(t^1);//*(1<<(lb-getlong(t)));
    }
    return re;
}
inline int change(ll s,ll t,ll k)//区间修改
{
    for(s=s+bit-1,t=t+bit+1;s^t^1;s>>=1,t>>=1)
    {
        //int tmp;
        if(!(s&1))
        {
            mark[s^1]+=k;//*(1<<(lb-getlong(s)));
            put(s^1,k);
        }
        if(t&1)
        {
            mark[t^1]+=k;//*(1<<(lb-getlong(t)));
            put(t^1,k);
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(bit=1;bit-2<n;bit<<=1);
    lb=getlong(bit);
    for(int i=bit+1;i<=bit+n;i++)
        cin>>a[i];
    for(int i=bit-1;i;i--)
    {
        a[i]=a[i<<1]+a[i<<1|1];//( i*2==i<<1) , (i*2+1==i<<1|1)
        //a[i<<1]-=a[i];a[i<<1|1]-=a[i];
    }
    for(int i=1;i<=m;i++)
    {
        ll aa,b,c,d;
        cin>>aa;
        if(aa==2)
        {
            cin>>b>>c;//cout<<b<<' '<<c<<' '<<get(b,c)<<endl;
            cout<<get(b,c)<<endl;
            for(int i=1;i<=n+bit;i++)cout<<get1(i)<<' ';cout<<endl;
        }
        else
        {
            cin>>b>>c>>d;change(b,c,d);
            //cout<<b<<' '<<c<<' '<<d<<endl;
            for(int i=1;i<=n+bit;i++)cout<<get1(i)<<' ';cout<<endl;
        }
    }

    //cout << "Hello world!" << endl;
    return 0;
}