数组计算机(sdut3771)

Problem Description

bLue 有一个神器的机器,这个机器可以读入一个数组,并按照用户要求快速地进行数组的处理和计算,它支持如下两种操作:

  • 操作 1:把数组中第 p 个元素的值增加 v。
  • 操作 2:计算数组中 [l, r] 区间内所有数的和。

这个机器就是这么的神奇,但是 bLue 的计算机坏掉了,你能帮他修一下吗?

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。

对于每组数据:

  • 第 1 行输入一个整数 n (1 <= n <= 10^5),表示数组中元素的个数。
  • 第 2 行输入 n 个用空格隔开的整数 ai (1 <= ai <= 10^10),表示初始输入到计算机中的数组。
  • 第 3 行输入一个整数 q (1 <= q <= 50000),表示用户的操作次数。
  • 接下来 q 行,每行输入先输入 1 个整数,表示操作类型,根据不同的操作类型:
    • 如果类型为 1,则紧接着输入 2 个用空格隔开的整数 p (1 <= p <= n) 和 v (1 <= v <= 10^10),表示要把数组中第 p 个数的值增加 v。
    • 如果类型为 2,则紧接着输入 2 个用空格隔开的整数 l, r (1 <= l <= r <= n),表示要计算区间 [l, r] 内所有数的和(数组下标从 1 开始)。

Output

对于每组数据中的每次类型为 2 的操作,输出 1 行,包含一个整数,表示计算出的和。

Example Input

5
1 2 3 4 5
5
2 1 2
2 1 5
1 4 10
2 4 5
2 1 5

Example Output

3
15
19
25
#include <stdio.h>
#include <stdlib.h>

long long int tree[400000];
long long int v;
void create(int root,int l,int r)
{
    if(l==r)
    {
        scanf("%lld",&tree[root]);
        return;
    }
    int mid=(l+r)/2;
    create(2*root,l,mid);
    create(2*root+1,mid+1,r);
    tree[root]=tree[2*root]+tree[2*root+1];
}
long long int find(int root,int l,int r,int L,int R)
{
    if(l<=L&&r>=R)
    {
        return tree[root];
    }
    int mid=(L+R)/2;
    long long int sum=0;
    if(l<=mid)
    {
        sum+=find(2*root,l,r,L,mid);
    }
    if(r>mid)
    {
        sum+=find(2*root+1,l,r,mid+1,R);
    }
    return sum;
}
void updata(int root,int d,int l,int r)//更新节点
{
    if(l==d&&r==d)//若已找到这个节点
    {
        tree[root]+=v;//修改数值
        return;
    }
    int mid=(l+r)/2;
    if(d<=mid)updata(2*root,d,l,mid);//左半查找
    if(d>mid)updata(2*root+1,d,mid+1,r);//右半
    tree[root]=tree[2*root]+tree[2*root+1];//更新受影响的根节点数值
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        create(1,1,n);
        int m,f,l,r,p;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&f);
            if(f==1)
            {
                scanf("%d%lld",&p,&v);
                updata(1,p,1,n);
            }
            else
            {
                scanf("%d%d",&l,&r);
                printf("%lld\n",find(1,l,r,1,n));
            }
        }
    }
    return 0;
}


/***************************************************
User name: jk170405贾辉
Result: Accepted
Take time: 580ms
Take Memory: 2208KB
Submit time: 2018-01-26 19:40:48
****************************************************/

发表评论

电子邮件地址不会被公开。 必填项已用*标注