UESTC_秋实大哥与线段树 2015 UESTC Training for Data Structures<Problem M>

M - 秋实大哥与线段树

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

“学习本无底，前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。

秋实大哥是一个爱学习的人，今天他刚刚学习了线段树这个数据结构。

为了检验自己的掌握程度，秋实大哥给自己出了一个题，同时邀请大家一起来作。

秋实大哥的题目要求你维护一个序列，支持两种操作：一种是修改某一个元素的值；一种是询问一段区间的和。

Input

第一行包含一个整数n，表示序列的长度。

接下来一行包含n个整数ai，表示序列初始的元素。

接下来一行包含一个整数m，表示操作数。

接下来m行，每行是以下两种操作之一：

1 x v : 表示将第x个元素的值改为v
2 l r : 表示询问[l,r]这个区间的元素和

1≤n，m，v，ai≤100000，1≤l≤r≤n。

Output

对于每一个2 l r操作，输出一个整数占一行，表示对应的答案。

Sample input and output

Sample Input	Sample Output
3 1 2 3 3 2 1 2 1 1 5 2 1 2	3 7

解题报告

本题...显然没有什么特别的技巧，直接上线段树即可解决，唯一注意的就是使用long long.

#include <iostream>
#include <cstring>

typedef long long ll;
using namespace std;
const int maxn = 5e5 + 15;
ll tree[maxn];

void updata(int pos,int v,int o,int l,int r)
{
  if (l == r)
   {
      tree[o] = v;
         return;
   }
  int mid = l + (r-l)/2;
  if (pos <= mid)
   updata(pos,v,2*o,l,mid);
  else
   updata(pos,v,2*o+1,mid+1,r);
  tree[o] = tree[2*o] + tree[2*o+1];
}

ll query(int ql,int qr,int o,int l,int r)
{
   if (ql <= l && r <= qr)
    return tree[o];
   ll res = 0;
   int mid = l + (r-l) / 2;
   if (ql <= mid)
    res += query(ql,qr,2*o,l,mid);
   if (qr > mid)
   res += query(ql,qr,2*o+1,mid+1,r);
   return res;
}


int main(int argc,char *argv[])
{
  int n,m;
  memset(tree,0,sizeof(tree));
  scanf("%d",&n);
  for(int i = 1 ; i <= n ; ++ i)
   {
         int temp;
         scanf("%d",&temp);
         updata(i,temp,1,1,n);
   }
  scanf("%d",&m);
  while(m--)
   {
          int i,j,k;
          scanf("%d%d%d",&i,&j,&k);
          if (i == 1)
           updata(j,k,1,1,n);
       else
        {
           ll ans = query(j,k,1,1,n);
           printf("%lld
",ans);
        }
   }
  return 0; 
}