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 + ;

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)/;

  if (pos <= mid)

   updata(pos,v,*o,l,mid);

  else

   updata(pos,v,*o+,mid+,r);

  tree[o] = tree[*o] + tree[*o+];

}

ll query(int ql,int qr,int o,int l,int r)

{

   if (ql <= l && r <= qr)

    return tree[o];

   ll res = ;

   int mid = l + (r-l) / ;

   if (ql <= mid)

    res += query(ql,qr,*o,l,mid);

   if (qr > mid)

   res += query(ql,qr,*o+,mid+,r);

   return res;

}

int main(int argc,char *argv[])

{

  int n,m;

  memset(tree,,sizeof(tree));

  scanf("%d",&n);

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

   {

         int temp;

         scanf("%d",&temp);

         updata(i,temp,,,n);

   }

  scanf("%d",&m);

  while(m--)

   {

          int i,j,k;

          scanf("%d%d%d",&i,&j,&k);

          if (i == )

           updata(j,k,,,n);

       else

        {

           ll ans = query(j,k,,,n);

           printf("%lld\n",ans);

        }

   }

  return ;

}

巴特西

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

M - 秋实大哥与线段树

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

Input

Output

Sample input and output

最新文章

热门文章