线段树练习

1.单点修改+区间查询

P3374 【模板】树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 x

• 求出某区间每一个数的和

  输入格式

  第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。

  第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

  接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：

  • 1 x k 含义：将第 x 个数加上 k

  • 2 x y 含义：输出区间 [x,y] 内每个数的和

    输出格式

    输出包含若干行整数，即为所有操作 22 的结果。

    输入输出样例

    输入 #1

    5 5
    1 5 4 2 3
    1 1 3
    2 2 5
    1 3 -1
    1 4 2
    2 1 4

    输出 #1

    14
    16

    说明/提示

    【数据范围】

    对于 30% 的数据，1≤n≤8，1≤m≤10；

    对于 70% 的数据，1≤n,m≤10^4；

    对于 100% 的数据，1≤n,m≤5×10^5。

    数据保证对于任意时刻，a 的任意子区间（包括长度为 1 和 n 的子区间）和均在 [−231,231) 范围内。

    样例说明：

    

    故输出结果14、16

    解题思路

    单点修改操作：递归到叶子结点，然后对叶子结点进行修改，然后返回的时候又改变其父节点

    void find(int p, int x, int k)
    {
    	if (a[p].l == a[p].r)//到叶子结点，直接修改
    	{
    		a[p].data += k;
    		return;
    	}
    	if (x = l && a[p].r = l && a[p].r