CDOJ 1073 线段树单点更新+区间查询水题

Appoint description:
System Crawler (2016-04-24)

Description

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

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

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

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

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

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

Sample Input

3
1 2 3
3
2 1 2
1 1 5
2 1 2

Sample Output

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int maxn=100000;

struct Tree{

   int l,r;

   ll sum;//注意sum要用ll

   int mid()

   {

       return (l+r)>>1;

   }

}tree[4*maxn+10];

void pushup(int k)

{

   tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;

}

void build(int k,int l,int r)

{

   tree[k].l=l;tree[k].r=r;

   if(l==r) scanf("%lld",&tree[k].sum);

   else

   {

       int mid=tree[k].mid();

       build(2*k,l,mid);

       build(2*k+1,mid+1,r);

       pushup(k);

   }

}

void update(int id,int pos,int val)

{

   if(tree[id].l==tree[id].r)

        tree[id].sum=val;

   else

   {

       int mid=tree[id].mid();

       if(pos<=mid) update(2*id,pos,val);

       else update(2*id+1,pos,val);

       pushup(id);

   }

}

ll query(int id,int l,int r)

{

   if(l<=tree[id].l&&tree[id].r<=r)

        return tree[id].sum;

   else

   {

       int mid=tree[id].mid();

       ll sl=0,sr=0;

       if(l<=mid) sl=query(2*id,l,r);

       if(r>mid) sr=query(2*id+1,l,r);//跟单点更新的update有点不同，单点更新的是只//能走一个方向

       pushup(id);

       return sl+sr;

   }

}

int main()

{

    int n,m;

    while(~scanf("%d",&n))

    {

        build(1,1,n);

        scanf("%d",&m);

        while(m--)

        {

            int op,x,y;

            scanf("%d %d %d",&op,&x,&y);

            if(op==1)

                update(1,x,y);

            else

                printf("%lld\n",query(1,x,y));

        }

    }

    return 0;

}

巴特西

CDOJ 1073 线段树单点更新+区间查询水题

最新文章

热门文章

巴特西

CDOJ 1073 线段树 单点更新+区间查询 水题

最新文章

热门文章

CDOJ 1073 线段树单点更新+区间查询水题