問題A:数列操作

問題A:数列操作
時間制限: 1セット  メモリ制限: 128 MB提出: 63  解決: 22[提出][状態][討論版][出題者:quanxing][Edit][TestData]
テーマリンク:http://acm.ocrosoft.com/problem.php?cid=1688&pid=0
テーマの説明
   n個の数列を指定すると、2つの動作が規定されています.1つは、ある要素を修正すること、2つはサブ数列［A,B］の連続和を求めることです.数列の元素数は最大10万個で、問合せは最大10万回までです.
入力
1行目は整数n、m(nは入力nの数列、mはmの操作があることを示します.)2行目はnの数列を入力します. 次のM行は、より良い行ごとに3つの数k、a、b(k=0はサブ数列[a、b]の和を表し、k=1はa番目の数列プラスbを表します.)
出力
いくつかの行の数字を出力して、K=0の度に1つのサブ数列[a,b]を出力する連続和を表します.
サンプル入力

10 5

1 2 3 4 5 6 7 8 9 10

1 1 5

0 1 3

0 4 8

1 7 5

0 4 8

サンプル出力

11

30

35

考え方:ツリー配列のすべての操作を追加すればいいです.
コード:

#include

using namespace std;

#define maxn 100005

int A[maxn], C[maxn];

int n, m;

int lowbit(int t)//t       ，     0 k ，  2^k  

{

    return t & -t;

}

void add(int x, int y)//    

{

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

    {

         C[i] += y;

    }

}

int sum(int x)//    

{

    int ans = 0;

    for (int i = x; i > 0; i -= lowbit(i))

    {

         ans += C[i];

    }

    return ans;

}

int main()

{

    scanf("%d%d", &n, &m);// scanf，  cin cout

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

    while (m--)

    {

         int k;

         int a, b;

         scanf("%d%d%d", &k, &a, &b);

         if (k == 1)

         {

             add(a, b);

         }

         else

         {

             printf("%d
", sum(b) - sum(a - 1));

         }

    }

}