CDOJ 838母儀天下樹状配列(2014データ構造テーマ

天下の儀
Time Limit:1 Sec  メモリLimit:162 MB
タイトル接続
http://acm.uestc.edu.cn/#/problem/show/838
Description
富庶の城内には、相容れない長街があり、蚤の街と呼ばれ、戦争による孤児が集まっています.全国の経済は戦争のために奉仕している時には、ここまで手が回らなくなりました.
二人の奥さんを除いて.
ジョーさんは毎日いくつかの食べ物を持ってフリーストリートに来て、ある子供に配っています.配分のムラを避けるために、彼女たちは時々一つの地域の食べ物の総量を聞いて調整して、子供一人に十分な食べ物があるようにします.
Input
最初の行には整数nがあります.mはノミの街にn戸の子供が住んでいます.ジョーさんは全部で配ったり聞いたりしました.
第二行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≦i≦n
1≦n,m≦100000,0≦ai≦100000,1≦xi≦n,0≦wi≦10000,1≦li≦i≦n
Output
問い合わせがあれば何行出力し、各行に整数を出力し、その問い合わせに対する回答とします.
Sample Input

5 4

1 2 3 4 5

1 2 3

0 2 4

1 4 1

0 1 5

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=0,f=1;char ch=getchar();

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

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

    return x*f;

}

int buf[10];

inline void write(int i) {

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

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

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

  printf("
");

}

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=0;

    while(x>0)

    {

        s+=a[x];

        x-=lowbit(x);

    }

    return s;

}



int main()

{

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

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

    {

        int x=read();

        add(i,x);

    }

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

    {

        int x=read();

        if(x==0)

        {

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

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

        }

        else

        {

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

            add(c,d);

        }

    }

    return 0;

}