cogs 264. 数列操作单点修改区间查询

发布时间：2020-12-13 22:16:40 所属栏目：PHP教程来源：网络整理

导读：http://cogs.pro:8080/cogs/problem/problem.php?pid=pyNimmVeq ? 264. 数列操作 ★☆?? 输入文件： shulie.in ?? 输出文件： shulie.out ??? 简单对比时间限制：1 s?? 内存限制：160 MB 【问题描述】给定一个数列? A ，请实现如下两种操作： 1. 将? A k ?

http://cogs.pro:8080/cogs/problem/problem.php?pid=pyNimmVeq

?

264. 数列操作

★☆?? 输入文件：shulie.in?? 输出文件：shulie.out???简单对比
时间限制：1 s?? 内存限制：160 MB

【问题描述】

给定一个数列?

1. 将?

2. 查询?

【输入格式】

第一行为一个整数?

第二行有?

第三行为一个整数?

下面?

ADD k d（表示将?

SUM s t（表示查询?

【输出格式】

对于每一个询问，输出查询的结果。

【样例输入】

4
1 4 2 3
3
SUM 1 3
ADD 2 50
SUM 2 3

【样例输出】

7
56


那么非常显然 这就是一道模板题
单点修改 区间查询   （其实也就是一个树状数组或者线段树板子）
不多说了 来粘一段代码吧

1.线段树

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,m,a[maxn];
struct SegmentTree{
    int l,r;
    long long dat;
}t[maxn<<2];
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].dat=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
void Add(int p,int x,int v){
    if(t[p].l==t[p].r){
        t[p].dat+=v;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid)
        Add(p*2,x,v);
    else Add(p*2+1,v);
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
long long Ask(int p,int r){
    if(l<=t[p].l&&r>=t[p].r)
        return t[p].dat;
    int mid=(t[p].l+t[p].r)>>1;
    long long val=0;
    if(l<=mid)
        val+=Ask(p*2,r);
    if(r>mid)
        val+=Ask(p*2+1,r);
    return val;
}
int main()
{
    freopen("shulie.in","r",stdin);
    freopen("shulie.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        string s;cin>>s;
        if(s[0]==‘S‘){
            int l,r;scanf("%d%d",&l,&r);
            printf("%lldn",Ask(1,r));
        }
        else{
            int x,v;scanf("%d%d",&x,&v);
            Add(1,v);
        }
    }
    return 0;
}

2.树状数组

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,a[maxn];
long long sum[maxn];
int lowbit(int x){ return x&(-x);}
void Add(int x,int d){
    while(x<=n){sum[x]+=d;x+=lowbit(x); }
}
long long Sum(int x){
    long long ret=0;
    while(x>0){ ret+=sum[x];x-=lowbit(x);}
    return ret;
}
int main()
{
    freopen("shulie.in",&a[i]),Add(i,a[i]);
    scanf("%d",Sum(r)-Sum(l-1));
        }
        else{
            int x,&v);
            Add(x,v);
        }
    }
    
    return 0;
}

666 加油吧背板子走天下

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

cogs 264. 数列操作 单点修改 区间查询