当前位置: 代码迷 >> 综合 >> UESTC-1073-秋实大哥与线段树
  详细解决方案

UESTC-1073-秋实大哥与线段树

热度:25   发布时间:2023-12-07 01:36:40.0

A -秋实大哥与线段树

 UESTC - 1073?

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

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

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

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

Input

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

接下来一行包含nn个整数aiai,表示序列初始的元素。

接下来一行包含一个整数mm,表示操作数。

接下来mm行,每行是以下两种操作之一:

1 x v : 表示将第x个元素的值改为v

2 l r : 表示询问[l,r]这个区间的元素和

1≤n,m,v,ai≤1000001≤n,m,v,ai≤100000,1≤l≤r≤n1≤l≤r≤n。

Output

对于每一个22 ll rr操作,输出一个整数占一行,表示对应的答案。

Sample Input

3

1 2 3

3

2 1 2

1 1 5

2 1 2

Sample Output

3

7

 

 

#include <iostream>#include <cstdio>

#define lid (id << 1)#define rid (id << 1 | 1)

using namespace std;

const int N=100005;struct node

{

    int l,r;

    long long sum;

}tr[N * 4];int a[N];

void push_up(int id){

    tr[id].sum = tr[lid].sum + tr[rid].sum;

}

void build(int id, int l,int r){

    tr[id].l = l; tr[id].r = r;

    if(l == r)

    {

        tr[id].sum = a[l];

        return;

    }

    int mid = (l + r) >>1;

    build(lid, l, mid);

    build(rid, mid +1, r);

    push_up(id);

}

void updata(int id,int x,int v){

    if(tr[id].l == tr[id].r){

        tr[id].sum = v;

        return;

    }

    int mid = (tr[id].l + tr[id].r) >>1;

    updata(x <= mid ? lid : rid, x, v);

    push_up(id);

}

long long query(int id, int l, int r){

    if(tr[id].l == l && tr[id].r == r)

        return tr[id].sum;

    int mid = (tr[id].l + tr[id].r) >>1;

    if(r <= mid)    return query(lid, l, r);

    if(l > mid)     return query(rid, l, r);

    return query(lid, l, mid)+query(rid, mid +1,r);

}

int main(){

    int n,m;

    int p,x,y;

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

    build(1,1,n);

    scanf("%d",&m);

    while(m --)

    {

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

        if(p ==1)

            updata(1, x, y);

        else

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

    }

    return 0;

}


顺便推荐一篇比较详细的讲解线段树知识点的文章。


线段树入门(一):http://www.cnblogs.com/shadowland/p/5870339.html

  相关解决方案