欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树状数组Binary Indexed Tree(1):单点修改,区间查询

程序员文章站 2024-03-03 16:14:58
...

Description:

给定数列a[1],a[2]…,a[n],需要依次执行q个操作。
操作分两类:
1 i x : 将a[i]加上x
2 l r :给定l,r,求 ∑ i = l r \sum_{i=l}^r i=lra[i]的值

(1 ≤ \leq n,q ≤ \leq 106)

代码

// TSWorld
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000009;

long long tree[N];
long long number[N];
int n,q;

inline int lowbit(int x) {
	return x&(-x);
}
void Change(int index,long long delta) {
	while(index <= n) {
		tree[index] += delta;
		index += lowbit(index);
	}
}

long long Query(int index)
{
	long long sum = 0;

	while(index > 0) {
		sum += tree[index];
		index -= lowbit(index);
	}
	return sum;
}
int main()
{
	int cmd = 0,l = 0,r = 0;
	cin>>n>>q;

	for(int i = 1;i <= n;i++) {
		scanf("%lld",&number[i]);
		Change(i,number[i]);
	}

	for(int i = 1;i <= q;i++) {
		scanf("%d%d%d",&cmd,&l,&r);

		if(cmd == 1)
			Change(l,r);
		else
			printf("%lld\n",Query(r) - Query(l-1));
	}

	return 0;
}