线段树练习题C

                                   Problem C: 你有没有好好听课

                                                     Time Limit: 2 Sec  Memory Limit: 128 MB
 

Description

为了检验你上午有没有好好听我讲课，于是有了这一题。给你一个数组a[1]~a[N],有q次操作，每次操作有两种类型，第一种询问操作，询问区间[l, r]之间数的和，第二种操作是修改操作，将位置loc的数改为x。对，你没有听错，就是这么简单，简单的话就赶快ac吧。

Input

第一行一个整数T，代表测试数据的组数.
接下来T组测试数据.
每组测试数据第一行两个整数N, q（N, q <= 1e5）,分别代表数组a的长度和操作的个数
接下来一行为N个整数，代表数组a
接下来q行，每一行格式为下面两种格式中的一种
1 loc x 将loc位置的数改为x，即a[loc] = x(1 <= loc <= N, 1 <= x <= 1e5)
2 l, r 询问区间[l, r]之间数的和（1 <= l <= r <= N)

Output

对于每组测试数据的询问操作，输出结果

解答：

这就是最基本的模板题

#include<iostream>
using namespace std;
const long long  Max=100000;
struct Node
{
    int L,R;
    int sum;
}Node[Max<<2];
int a[Max+5];
void pushUp(int i)
{
    int lson = i<<1;
    int rson = lson + 1;
    Node[i].sum = Node[lson].sum + Node[rson].sum;
}
 
void build(int i, int l, int r)
{
    Node[i].L = l;
    Node[i].R = r;
    Node[i].sum = 0;
    if(l == r)
    {
        Node[i].sum = a[l];
        return;
    }
    int mid = (l + r)>>1;
    build(i<<1, l, mid);
    build((i<<1)|1, mid + 1, r);
    pushUp(i);
}
void update(int i,int loc,int value)
{
    if(Node[i].L == Node[i].R)
    {
        Node[i].sum =value;
        return;
    }
    int mid = (Node[i].L + Node[i].R)>>1;
    if(loc <= mid) update(i<<1, loc, value);
    else update((i<<1)|1, loc, value);
    pushUp(i);
}
int query(int i, int l, int r)
{
 
    if(Node[i].L == l && Node[i].R == r)
    {
        return Node[i].sum;
    }
    int mid = (Node[i].L + Node[i].R)>>1;
    if(r <= mid) return query(i<<1, l, r);
    else if(l > mid) return query((i<<1)|1, l, r);
    else
    {
        return query(i<<1, l, mid) + query((i<<1)|1, mid + 1, r);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int N,q;
        cin>>N>>q;
        for(int i=1;i<=N;i++)
        {
            cin>>a[i];
        }
        build(1,1,N);
        for(int i=1;i<=q;i++)
        {
            int m,p,q;
            cin>>m>>p>>q;
            if (m==1)
                {
            update(1, p, q);
                }
           if (m==2)
            {
                cout<<query(1,p,q)<<endl;
            }
        }
    }
    return 0;
}