【单点修改，区间查询例题】

1.单点修改、区间查询 - hdu 1166 敌兵布阵

2.单点修改、区间查询最值 - hdu 1754 I Hate It

【hdu 1166 敌兵布阵】

【代码】

const int maxn=50000;int n,a[maxn+10];int sum[4*maxn+10];void build(int k,int l,int r){    if(l==r)    {        sum[k]=a[l];        return;    }    int mid=l+r>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    sum[k]=sum[k<<1]+sum[k<<1|1];}void change(int k,int l,int r,int x,int v){    if(r
   
    x) return;    if(l==r&&l==x)    {        sum[k]+=v;        return;    }    int mid=l+r>>1;    change(k<<1,l,mid,x,v);    change(k<<1|1,mid+1,r,x,v);    sum[k]=sum[k<<1]+sum[k<<1|1];}int query(int k,int l,int r,int x,int y){    if(y
    
     r) return 0;    if(l>=x&&r<=y) return sum[k];    int mid=l+r>>1;    int res;    res=query(k<<1,l,mid,x,y);    res+=query(k<<1|1,mid+1,r,x,y);    return res;}int main(){    int t; scanf("%d",&t);    for(int _=1;_<=t;_++)    {        scanf("%d",&n);        for(int i=1;i<=n;i++) scanf("%d",&a[i]);        build(1,1,n);        printf("Case %d:\n",_);        char s[10];        while(~scanf("%s",s))        {            int x,y;            if(s[0]=='E') break;            scanf("%d%d",&x,&y);            if(s[0]=='A') change(1,1,n,x,y);            else if(s[0]=='S') change(1,1,n,x,-y);            else printf("%d\n",query(1,1,n,x,y));        }    }    return 0;}

【hdu 1754 I Hate It 】

线段树单点修改区间查询最值模板题。

【代码】

const int maxn=200000;int n,a[maxn+10];int ma[4*maxn+10];void build(int k,int l,int r){    if(l==r)    {        ma[k]=a[l];        return;    }    int mid=l+r>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    ma[k]=max(ma[k<<1],ma[k<<1|1]);}void change(int k,int l,int r,int x,int v){    if(r
   
    x) return;    if(l==r&&l==x)    {        ma[k]=v;        return;    }    int mid=l+r>>1;    change(k<<1,l,mid,x,v);    change(k<<1|1,mid+1,r,x,v);    ma[k]=max(ma[k<<1],ma[k<<1|1]);}int query(int k,int l,int r,int x,int y){    if(y
    
     r) return 0;    if(l>=x&&r<=y) return ma[k];    int mid=l+r>>1;    int res;    res=max(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));    return res;}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        for(int i=1;i<=n;i++) scanf("%d",&a[i]);        build(1,1,n);        while(m--)        {            char c; int x,y;            scanf(" %c%d%d",&c,&x,&y);            if(c=='U') change(1,1,n,x,y);            else printf("%d\n",query(1,1,n,x,y));        }    }    return 0;}

【区间修改，区间查询例题】

【hdu 1698 Just a Hook】

区间修改、区间查询区间和

【标记下传】

const int maxn=100000;int n,a[maxn+10];int add[4*maxn+10],sum[4*maxn+10];void build(int k,int l,int r){    if(l==r)    {        sum[k]=1;        return;    }    int mid=l+r>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    sum[k]=sum[k<<1]+sum[k<<1|1];}void Add(int k,int l,int r,int v)        //把区间[l,r]所有数变成v{    add[k]=v;          //打标记    sum[k]=(r-l+1)*v;  //维护区间和    return;}void pushdown(int k,int l,int r,int mid) //标记下传{    if(add[k]==0) return;         //没有标记则不用考虑    Add(k<<1,l,mid,add[k]);       //下传到左子树    Add(k<<1|1,mid+1,r,add[k]);   //下传到右子树    add[k]=0;                     //清零}void modify(int k,int l,int r,int x,int y,int v)  //给定区间[x,y]所有数变成v{    if(l>=x&&r<=y) return Add(k,l,r,v);    int mid=l+r>>1;    pushdown(k,l,r,mid);          //到达每一个结点都要下传标记    if(x<=mid) modify(k<<1,l,mid,x,y,v);    if(mid
   
    =x&&r<=y) return sum[k];    int mid=l+r>>1,res=0;    pushdown(k,l,r,mid);       //下传标记    if(x<=mid) res+=query(k<<1,l,mid,x,y);    if(mid

【~~】