线段树求查错

树状数组1

#include <bits/stdc++.h>
using namespace std;

const int maxn = 4 * 5e5 ;
int n, m;

struct node
{
	int l, r;
	int val;
};

node tree[maxn];
int a[maxn];

void build(int i, int l, int r)
{
	tree[i].l = l;
	tree[i].r = r;
	if(l == r)
	{
		tree[i].val = a[i];
		return;
	}
	int mid = (l + r) >> 1;
	build(i * 2, l, mid);
	build(i * 2 + 1, mid + 1, r);
	tree[i].val = tree[i * 2].val + tree[i * 2 + 1].val;
	return;
}

void update(int i, int dis, int k)
{
	if(tree[i].l == tree[i].r)
	{
		tree[i].val += k;
		return;
	}
	if(dis <= tree[i * 2].r)update(i * 2, dis, k);
	else update(i * 2 + 1, dis, k);
	tree[i].val = tree[i * 2].val + tree[i * 2 + 1].val;
	return;
}

int search(int i, int l, int r)
{
	if(tree[i].l >= l && tree[i].r <= r)
		return tree[i].val;
	if(tree[i].l < l || tree[i].r > r)
		return 0;
	int sum = 0;
	if(tree[i * 2].r >= l)sum += search(i * 2, l, r);
	if(tree[i * 2 + 1].l <= r)sum += search(i * 2 + 1, l, r);
	return sum;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &a[i]);
	}
	build(1, 1, n);
	for (int i = 1; i <= n ;i ++)
	{
		printf("%d ", tree[i].val);
	}
	while(m --)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if(x == 1)
		{
			update(1, y, z);
		}
		else
		{
			printf("%d\n", search(1, y, z));
		}
	}
	return 0;
}

输出全为零