Skip to main content

备战 NOIP2017 - zkw 线段树

· 4 min read

本来不准备写备战 NOIP2017 系列了,无奈刷题刷爽了...

线段树#

维护区间修改查询的数据结构

第一行包含两个整数 N、M,分别表示该数列数字的个数和操作的总个数
第二行包含 N 个用空格分隔的整数,其中第 i 个数字表示数列第 i 项的初始值
接下来 M 行每行包含 3 或 4 个整数,表示一个操作,具体如下:

  1. 格式:1 x y k 含义:将区间[x,y]内每个数加上 k
  2. 格式:2 x y 含义:输出区间[x,y]内每个数的和
#include<iostream>#include<cstdio>using std::cin;using std::cout;
typedef long long ll;
const int N=100000+10;
struct P{    int lc,rc;    int l,r;    ll sum,v;};
P tree[N*2];int tail=0;
int build_tree(int l,int r){    P &now=tree[tail++];    now.l=l;now.r=r;    if(l+1<r){        int mid=l+(r-l)/2;        now.lc=build_tree(l,mid);        now.rc=build_tree(mid,r);    }    return &now-tree;}
void update(int p){    P &now=tree[p];    now.sum=now.v*(now.r-now.l);    if(now.l+1<now.r)now.sum+=tree[now.lc].sum+tree[now.rc].sum;}
void push_down(int p){    P &now=tree[p];    tree[now.lc].v+=now.v;    tree[now.rc].v+=now.v;    now.v=0;    update(now.lc);    update(now.rc);}
void add(int l,int r,ll v,int p=0){    P &now=tree[p];    if(l==r)return;    if(now.l>=r||now.r<=l)return;    if(now.l>=l&&now.r<=r){        now.v+=v;    }else{        push_down(p);        add(l,r,v,now.lc);        add(l,r,v,now.rc);    }    update(p);}
ll query(int l,int r,int p=0){    P &now=tree[p];    if(l>=r)return 0;    if(now.l>=r||now.r<=l)return 0;    if(now.l>=l&&now.r<=r)return now.sum;    push_down(p);    ll ret=query(l,r,now.lc)+query(l,r,now.rc);    update(p);    return ret;}
int main(){    std::ios::sync_with_stdio(false);    int n,m;    cin>>n>>m;    build_tree(1,n+1);    for(int i=1;i<=n;i++){        ll buf;        cin>>buf;//scanf("%d",&buf);        add(i,i+1,buf);    }    for(int k=0;k<m;k++){        int t,l,r;        cin>>t>>l>>r;        if(t==1){            ll v;            cin>>v;            add(l,r+1,v);        }else{            cout<<query(l,r+1)<<'\n';        }        //print();    }    return 0;}

详解看这里

zkw 线段树#

2013 年,《统计的力量》横空出世
zkw 线段树看起来很像树状数组(不知为什么...
zkw 线段树通过挖掘二叉树在数组中的特性,找到了一种可以快速定位叶子节点的方法,于是自顶向下的方法被抛弃,转而使用自底向上的方法

改段求点#

#include<cstdio>
const int N=500000+10;
int tree[N*3];int len=1;
void build(int n,int v=0){    while(len<n+2)len<<=1;    for(int i=len+1;i<=len+n;i++)scanf("%d",&tree[i]);}
void add(int l,int r,int v){    for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){        if(~l&1)tree[l+1]+=v;        if(r&1)tree[r-1]+=v;    }}
int query(int n,int res=0){    for(n+=len;n;n>>=1)res+=tree[n];    return res;}
int main(){    int n,m;    scanf("%d%d",&n,&m);    build(n);    for(int i=0;i<m;i++){        int t,x;        scanf("%d%d",&t,&x);        if(t==1){            int y,v;            scanf("%d%d",&y,&v);            add(x,y,v);        }else printf("%d\n",query(x));    }    return 0;}

改点求段#

#include<cstdio>
const int N=500000+10;
int tree[N*3];int len=1;
inline int Min(int a,int b){return a>b?b:a;}
void build(int n){    while(len<n+2)len<<=1;    for(int i=len+1;i<=len+n;i++)scanf("%d",&tree[i]);    for(int i=len;i>0;i--)tree[i]=tree[i<<1]+tree[i<<1^1];}
void add(int n,int v){    tree[n+len]+=v;    for(n+=len;n>1;n>>=1)        tree[n>>1]=tree[n]+tree[n^1];}
int query(int l,int r,int res=0){    for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){        if(~l&1)res+=tree[l+1];        if(r&1)res+=tree[r-1];    }    return res;}
int main(){    int n,m;    scanf("%d%d",&n,&m);    build(n);    for(int i=0;i<m;i++){        int t,x,y;        scanf("%d%d%d",&t,&x,&y);        if(t==1)add(x,y);        else printf("%d\n",query(x,y));    }    return 0;}

改段求段#

#include<cstdio>#include<iostream>using namespace std;
const int N=100000+10;
typedef long long ll;
ll val[N*4],sum[N*4];ll len[N*4];ll length=1;
long long  read(){    char ch=getchar();    long long  a=0,f=1;    while (ch<'0'||ch>'9')     {        if (ch=='-') f=-1;        ch=getchar();    }    while (ch>='0'&&ch<='9')     {        a=a*10+ch-'0';        ch=getchar();     }     return a*f;}
void build(int n){    while(length<n+2)length<<=1;    for(int i=length+1;i<=length+n;i++){            val[i]=read();            sum[i]=val[i];        }    for(int i=length;i>0;i--)sum[i]=sum[i<<1]+sum[i<<1^1];    for(int i=length+length-2;i>length;i--)len[i]=1;    for(int i=length-1;i>0;i--)len[i]=len[i<<1]+len[i<<1^1];}
void add(ll l,ll r,ll v){    for(l+=length-1,r+=length+1;l^r^1;l>>=1,r>>=1){        if(~l&1){            val[l+1]+=v;            sum[l+1]+=v*len[l+1];        }        if(r&1){            val[r-1]+=v;            sum[r-1]+=v*len[r-1];        }        sum[l>>1]=sum[l]+sum[l^1]+val[l>>1]*len[l>>1];        sum[r>>1]=sum[r]+sum[r^1]+val[r>>1]*len[r>>1];    }    while(l>1)sum[l>>1]=sum[l]+sum[l^1]+val[l>>1]*len[l>>1],l>>=1;}
ll query(ll l,ll r){    ll resl=0,resr=0;    ll lenl=0,lenr=0;    for(l+=length-1,r+=length+1;l^r^1;l>>=1,r>>=1){        if(~l&1){            resl+=sum[l+1];            lenl+=len[l+1];        }        if(r&1){            resr+=sum[r-1];            lenr+=len[r-1];        }        resl+=lenl*val[l>>1];        resr+=lenr*val[r>>1];    }    resl+=resr;    lenl+=lenr;    while(l>1)resl+=lenl*val[l>>1],l>>=1;    return resl;}
int main(){    int n,m;    scanf("%d%d",&n,&m);    build(n);    for(int i=0;i<m;i++){        int t=read(),x=read(),y=read();        if(t==1){            ll v;            v=read();            add(x,y,v);        }else printf("%lld\n",query(x,y));    }    return 0;}