problem.php?pid=pyNimmVeq

264. 数列操作

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

【问题描述】

给定一个数列 A，请实现如下两种操作：

1. 将 Ak 的值加 d。

2. 查询 As+As+1+⋯+At(s≤t) 的值。

【输入格式】

第一行为一个整数 n(0≤n≤100000)，表示数列 A 的大小。

第二行有 n 个整数，表示序列 A 各项的初始值。

第三行为一个整数 m(0≤m≤150000)，表示操作数。

下面 m 行，每行描述一个操作：

ADD k d（表示将 Ak 的值增加 d，1≤k≤n，d 为整数）

SUM s t（表示查询 As+⋯+At 的值）

【输出格式】

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

【样例输入】

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<<];

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)>>;

    build(p*,l,mid);

    build(p*+,mid+,r);

    t[p].dat=t[p*].dat+t[p*+].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)>>;

    if(x<=mid)

        Add(p*,x,v);

    else Add(p*+,x,v);

    t[p].dat=t[p*].dat+t[p*+].dat;

}

long long Ask(int p,int l,int r){

    if(l<=t[p].l&&r>=t[p].r)

        return t[p].dat;

    int mid=(t[p].l+t[p].r)>>;

    long long val=;

    if(l<=mid)

        val+=Ask(p*,l,r);

    if(r>mid)

        val+=Ask(p*+,l,r);

    return val;

}

int main()

{

    freopen("shulie.in","r",stdin);

    freopen("shulie.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    build(,,n);

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        string s;cin>>s;

        if(s[]=='S'){

            int l,r;scanf("%d%d",&l,&r);

            printf("%lld\n",Ask(,l,r));

        }

        else{

            int x,v;scanf("%d%d",&x,&v);

            Add(,x,v);

        }

    }

    return ;

}

2.树状数组

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#define maxn 100005

using namespace std;

int n,m,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=;

    while(x>){ ret+=sum[x];x-=lowbit(x);}

    return ret;

}

int main()

{

    freopen("shulie.in","r",stdin);

    freopen("shulie.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]),Add(i,a[i]);

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        string s;cin>>s;

        if(s[]=='S'){

            int l,r;scanf("%d%d",&l,&r);

            printf("%lld\n",Sum(r)-Sum(l-));

        }

        else{

            int x,v;scanf("%d%d",&x,&v);

            Add(x,v);

        }

    }

    return ;

}

666 加油吧背板子走天下

巴特西

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

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

264. 数列操作

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

最新文章

热门文章

巴特西

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

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

264. 数列操作

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

最新文章

热门文章

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