洛谷.P3374 樹狀數組

題目描述

如題，已知一個數列，你需要進行下面兩種操作：

将某一個數加上 x

求出某區間每一個數的和

輸入格式

第一行包含兩個正整數 n,m分别表示該數列數字的個數和操作的總個數。

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

接下來 m 行每行包含 3 個整數，表示一個操作，具體如下：

1 x k 含義：将第 x個數加上 k

2 x y 含義：輸出區間 [x,y]内每個數的和

輸出格式

輸出包含若幹行整數，即為所有操作的結果。

輸入輸出樣例

輸入

5 5

1 5 4 2 3

1 1 3

2 2 5

1 3 -1

1 4 2

2 1 4

輸出

14

16

題解代碼如下

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int tr[N];
int n,m;
///樹狀數組核心操作
int lowbit(int x){
	return x & -x;
}
///添加
void add(int x,int c){
	for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
///求和 
int sum(int x){
	int res = 0;
	for(int i=x;i;i-=lowbit(i)) res+=tr[i];
	return res;
}
int main(){

	scanf("%d%d",&n,&m);
	///樹狀數組初始化
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		add(i,x);
	}
	while(m --){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a == 1) add(b,c);
		if(a == 2){
			///求出區間 b～c 的所有數之和
			long long ans = sum(c) - sum(b - 1);
			printf("%lld\n",ans);
		}
	}
	return 0;
}