CDOJ 838 母仪天下树状数组（2014数据结构专题

母仪天下

Time Limit: 1 Sec Memory Limit: 162 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/838

Description

富庶的建业城中，有一条格格不入的长街，名曰跳蚤街，被战争所致的孤儿，聚集于此。全国的经济都在为战争服务之时，也无人顾得了这里了。

除了两位夫人。

大乔小乔每天都会带着一些食物来到跳蚤街，分给某一位孩子。为了避免分配不均，她们时常会询问一个区域内食物的总量，然后进行调整以保证每个孩子都有足够的食物。

Input

第一行两个整数n，m，表示跳蚤街住着n户孩子，大乔小乔一共分发或询问了m次。

第二行n个整数，第i个数ai表示第i户孩子已有ai的食物。

接下来m行，每行开始先读入一个整数si，指明这是一次询问还是一次分发。

si=0，表明这是一次询问，然后读入两个整数li,ri，表示询问[li，ri]区间中的孩子们一共有多少食物。

si=1，表明这是一次分发，然后读入两个整数xi,wi，表示对第xi户孩子分发了wi的食物。

1≤n,m≤100000,0≤ai≤100000,1≤xi≤n,0≤wi≤10000,1≤li≤ri≤n

Output

有多少询问就输出多少行，每行输出一个整数，作为对该询问的回答。

Sample Input

Sample Output

12 19

HINT

题解：

啊，裸的线段树或者树状数组，乱搞就好啦

加了输入输出挂，结果和scanf的速度一样……

代码：

#include<stdio.h>

#include<iostream>

#include<math.h>

#include<map>

#include<stack>

using namespace std;

#define maxn 100005

inline long long read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int buf[];

inline void write(int i) {

  int p = ;if(i == ) p++;

  else while(i) {buf[p++] = i % ;i /= ;}

  for(int j = p-; j >=; j--) putchar('' + buf[j]);

  printf("\n");

}

int lowbit(int x)

{

    return x&(-x);

}

int n,m;

int a[maxn];

void add(int x,int y)

{

    while(x<=n)

    {

        a[x]+=y;

        x+=lowbit(x);

    }

}

int sum(int x)

{

    int s=;

    while(x>)

    {

        s+=a[x];

        x-=lowbit(x);

    }

    return s;

}

int main()

{

    n=read(),m=read();

    for(int i=;i<=n;i++)

    {

        int x=read();

        add(i,x);

    }

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

    {

        int x=read();

        if(x==)

        {

            int c=read(),d=read();

            write(sum(d)-sum(c-));

        }

        else

        {

            int c=read(),d=read();

            add(c,d);

        }

    }

    return ;

}

CDOJ 838 母仪天下 树状数组 （2014数据结构专题