树状数组

主要解决两类:

1:单点修改,区间求和

​ bit维护节点

#include<bits/stdc++.h>
using namespace std;
int bit[2000006];
int n,m;
int lowbit(int x){
	return x&(-x);
}

void add(int index,int k){
	for(int i = index;i <= n;i+=lowbit(i)){
		bit[i]+=k;
	}
}

int sum(int start,int end){
	int ans = 0;
	for(int i = end;i;i-=lowbit(i)){
		ans+=bit[i];
	}
	for(int j = start-1;j;j-=lowbit(j)){
		ans-=bit[j];
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		int tmp;
		cin>>tmp;
		add(i,tmp);
	}
	for(int i = 0;i<m;i++){
		int tmp;
		cin>>tmp;
		if(tmp==1){
			int index,num;
			cin>>index>>num;
			add(index,num);
		}
		else{
			int start,end;
			cin>>start>>end;
			cout<<sum(start,end)<<endl;
		}
	}
	return 0;
} 

2:区间修改,单点求和

​ bit维护一个差分

#include<bits/stdc++.h>
using namespace std;
int bit[2000006];
int n,m;
int lowbit(int x){
	return x&(-x);
}

void add(int index,int k){
	for(int i= index;i<=n;i+=lowbit(i)) bit[i]+=k;
}

int get(int index){
	int ans = 0;
	for(int i = index;i>=1;i-=lowbit(i)) ans+=bit[i];
	return ans;
}
int main(){
	cin>>n>>m;
	int last=0,tmp;
	for(int i = 1;i<=n;i++){
		cin>>tmp;
		add(i,tmp-last);
		last=tmp;
	}
	for(int i = 0;i<m;i++){
		int tmp;
		cin>>tmp;
		if(tmp==1){
			int start,end,k;
			cin>>start>>end>>k;
			add(start,k);
			add(end+1,-k);
		}
		else{
			int index;
			cin>>index;
			cout<<get(index)<<endl;
		}
	}
	return 0;
} 

都是区间时线段树