【树状数组维护区间和】树状数组模板

单点更新 区间查询

直接利用树状数组存储原数组

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size

int n,m,k;
int p[MS],tr[MS];

// 输入原数组 
void input(){
	for(int i=1;i<=n;i++) cin >> p[i];
}

// 取出 x 的最低位 1 ,返回 2^k
// ex: 1010 返回 2^1 ,1001 返回 2^0 
int lowbit(int x){
	return x&(-x);
}

// 建立树状数组 
void build(){
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=lowbit(j)){
			tr[j] += p[i]; // tr 中所有包含 p[i] 的都要加上 
		}
	}
}

// 修改点值 (+) 
void revise_point(int sub ,int val){
	p[sub] += val; // 更新原数组 
	for(int i=sub;i<=n;i+=lowbit(i)){
		tr[i] += val;
	}
}

// 求 原数组 p 1 ~ i 的值 
LL get_sum(int i){
	LL cnt = 0;
	while(i>0){
		cnt += tr[i];
		i -= lowbit(i);
	}
	return cnt;
}

// 输出原数组 p 当前状态 
void output(){
	for(int i=1;i<=n;i++){
		cout << p[i] << " ";
	}
	cout << endl;
}

int main() {
	// >> 数组长度 
	cin >> n;
	input();
	// 建树状数组 
	build();
	// 修改点值 
	// 参数: 下标 ,值 
	cin >> m >> k;
	revise_point(m,k);
	// >> 当前原数组状态
	output();
	// 求和 
	// >> 请求区间
	cin >> m >> k;
	cout << get_sum(k) - get_sum(m-1) << endl;

	return 0;
}

区间更新 单点查询

利用树状数组存储原数组的差分,这样修改区间时只需要修改两个位置

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size

int n,m,k;
int p[MS],tr[MS],a[MS];

// 输入原数组 
void input(){
	for(int i=1;i<=n;i++) cin >> p[i];
	// 得到差分后的数组 a  
	for(int i=1;i<=n;i++) a[i] = p[i] - p[i-1];
}

// 取出 x 的最低位 1 ,返回 2^k
// ex: 1010 返回 2^1 ,1001 返回 2^0 
int lowbit(int x){
	return x&(-x);
}

// 建立树状数组 
void build(){
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=lowbit(j)){
			tr[j] += a[i]; // tr 中所有包含 p[i] 的都要加上 
		}
	}
}

// 修改点值 (+) 
void revise_point(int sub ,int val){
	a[sub] += val; // 更新数组 a
	for(int i=sub;i<=n;i+=lowbit(i)){
		tr[i] += val;
	}
}

// 求 原数组 p 1 ~ i 的值 
LL get_sum(int i){
	LL cnt = 0;
	while(i>0){
		cnt += tr[i];
		i -= lowbit(i);
	}
	return cnt;
}

int main() {
	// >> 数组长度 
	cin >> n;
	input();
	// 建树状数组 
	build();
	// 修改区间值 
	int l,r,val;
	cin >> l >> r >> val;
	revise_point(l,val);
	revise_point(r+1,-val);
	// 单点查询 
	cin >> m;
	cout << get_sum(m) << endl;

	return 0;
}

区间更新 区间查询

依旧利用树状数组存储原数组的差分,维护两个数状数组，$sum1[i] = a[i]，sum2[i] = a[i]*(i-1)$; 为何维护 .

#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 100009
#define mss 17
using namespace std;
// Notice the data size

LL n,m,k;
LL p[MS],tr[MS],a[MS];
LL sum1[MS],sum2[MS];

// 取出 x 的最低位 1 ,返回 2^k
// ex: 1010 返回 2^1 ,1001 返回 2^0 
int lowbit(int x){
	return x&(-x);
}

// 输入原数组 
void input(){
	for(int i=1;i<=n;i++) cin >> p[i];
}

// 对原数组 p 利用差分 存入数组 a  
void dif(){
	for(int i=1;i<=n;i++) a[i] = p[i] - p[i-1];
}

// 更新树状数组 (+)
void updata(int sub,LL val){
	int x = sub; // x 不变 保存 sub 值 
	for(int i=sub;i<=n;i+=lowbit(i)){
		tr[i] += val;
		sum1[i] += val;
		sum2[i] += val*(x-1);
	}
}

// 求前缀和 
LL get_sum(int i){
	LL cnt = 0;
	int x = i;
	while(i>0){
		cnt += x*sum1[i] - sum2[i];
		i -= lowbit(i);
	}
	return cnt;
}

int main() {
	// >> 数组长度 
	cin >> n;
	input();
	dif();
	// 直接更新 
	for(int i=1;i<=n;i++){
		updata(i,a[i]);
	}
	// 区间加减 
	LL l, r, val;
	cin >> l >> r >> val;
	updata(l,val);
	updata(r+1,-val);
	// 区间求和 
	cin >> m >> k;
	cout << get_sum(k) - get_sum(m-1) << endl;
	
	
	return 0;
}