题目传送门
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3个整数，表示一个操作，具体如下：
操作1： 格式：1 x k 含义：将第x个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入 #15 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 414
16说明/提示
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例说明：
故输出结果14、16
题解：
嘿嘿，浅浅讲一下思路吧！
首先啊，怎么大的范围，出题人肯定不会让你轻易暴力就能过的，区间求和，修改，我们很容易想到用线段树来解题，浅浅说一下为什么用线段树吧！
首先，线段树，可以有效的节省时间，避免超时的情况出现（好像是废话，哈哈哈哈哈）
其次，线段树可以单点修改，单点查询，区间修改，区间查询，所以正好符合我们这题
那直接上代码！！
AC代码
#include<iostream>
using namespace std;
const int N = 5 * 1e6 + 10;
int a[N];
struct node {
int l, r;
int sum;
}tr[4*N];
void build(int i, int l, int r)//建树
{
tr[i].l = l;
tr[i].r = r;
if (tr[i].l == tr[i].r)//叶子节点
{
tr[i].sum = a[tr[i].l];
return;
}
int mid = (l + r) >> 1;
build(i << 1, l,mid);
build((i << 1) + 1, mid+1, r);
tr[i].sum = tr[i << 1].sum + tr[(i << 1) + 1].sum;
}
void add(int i, int l, int k)//l处加k,因为是加单点，所以父节点均可加k，一次结束
{
if (tr[i].l <= l && tr[i].r >= l)//如果包含该点
{
tr[i].sum += k;//加上
if (tr[i].l == tr[i].r)//叶子节点
return;
}
if(tr[i].l >l|| tr[i].r < l)
return;
add((i << 1), l, k);
add((i << 1) + 1, l, k);
}
int search(int i,int l, int r)
{
int s = 0;
if (tr[i].l > r || tr[i].r < l)
return 0;//不包含的情况
if (tr[i].l >= l && tr[i].r <= r)
{
return tr[i].sum;
}
if (tr[i<<1].r >= l)
s += search((i << 1), l, r);
if (tr[(i<<1)+1].l <= r)
s += search((i << 1) + 1, l, r);
return s;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);//建树
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
if (x == 1)
{
add(1,y, z);
}
if (x == 2)
{
int ans = 0;
ans = search(1,y, z);
cout << ans << endl;
}
}
return 0;
}