5.树状数组和离散化

1.离散化

​ 离线操作（存下操作，后执行）

//找出所有操作点，存下
//将相关点排序去重
//将大点转化为小点
//操作 全部转化到小点上 

https://www.starrycoding.com/problem/63

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5+9;

vector<int> X;//离散化得到小点（相关的点）
ll a[N];

struct Q//存下操作和询问
{
	ll a,b;
}add[N],que[N];

int getidx(ll x)
{
	//lower_bound 找出数组中第一个 >= x的元素的迭代器
	//返回值的范围是[1,X.size()]
	return lower_bound(X.begin(),X.end(),x) - X.begin() + 1;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n, q;cin >> n >> q;
	
	//n次操作发，在x点 加w
	for(int i = 1;i <= n;++i)
	{
		ll x,w;cin >> x >> w;
		X.push_back(x);//存下相关点
		add[i] = {x,w};//和上面分开存相关点，并且存下w，为之后离线操作准备
	}
	
	//q次询问，[l,r]内所有点的和
	//这里先存下询问区间，离线操作
	for(int i = 1;i <= q;++i)
	{
		ll l,r;cin >> l >> r;
		X.push_back(l);
		X.push_back(r);
		que[i] = {l,r};
	}
	
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()) ,X.end());//得到仅有相关点
	
	//在一条仅有相关点的数轴，给其中的相关点加上对应的值
	for(int i = 1;i <= n;++i)
	{
		int x = getidx(add[i].a);
		ll w = add[i].b;
		a[x] += w;
	}
	
	//相关点数值的前缀和
	for(int i = 1;i <= X.size();++i) a[i] += a[i-1];
	
	//离线操作，处理询问区间
	for(int i = 1;i <= q;++i)
	{
		int l = getidx(que[i].a);
		int r = getidx(que[i].b);
		cout << a[r] - a[l - 1] << '\n';
	}

}

2.树状数组（不能用0当下标）

维护区间和

• 单点修改O(1)
• 区间修改O(nlogn)
• 区间查询O(nlogn)

Ti的管辖区间：[i - lowbit(i) + 1 ,i]，长度：lowbit(i)

https://www.starrycoding.com/problem/40

//树状数组单点修改模板（维护原数组的前缀和）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+9;
ll a[N],t[N];ll n,q;

int lowbit(int x){return x&-x;} //留下二进制的倒数第一个1

void update(int k ,ll x){
	for(int i = k;i <= n;i += lowbit(i)) t[i] += x; //将树状数组t赋值
}

ll getsum(int k)
{
	ll res = 0;
	for(int i = k;i > 0;i -= lowbit(i)) res += t[i];//得到k的前缀和
	return res;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	for(int i = 1;i <= n;++i) update(i, a[i]);
	
	while(q--)
	{
		int op;cin >> op;
		if(op == 1)
		{
			ll k,v;cin >> k >> v;
			update(k,v);
		}else
		{
			ll l,r;cin >> l >> r;
			cout << getsum(r) - getsum(l-1) << '\n';
		}
	}
}

//树状数组维护差分
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5+9;
ll a[N],td[N],tid[N];ll n,q;

int lowbit(int x){return x&-x;}

void update(int k ,ll x){
	for(int i = k;i <= n;i += lowbit(i)) td[i] += x,tid[i] += k * x;
}

ll getsum(int k)
{
	ll res = 0;
	for(int i = k;i > 0;i -= lowbit(i)) res += (k+1) * td[i] - tid[i];
	return res;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;++i) cin >> a[i];
	
	for(int i = 1;i <= n;++i) update(i, a[i]),update(i + 1, -a[i]);
	
	while(q--)
	{
		int op;cin >> op;
		if(op == 1)
		{
			ll l,r,v;cin >> l >> r >> v;
			update(l,v),update(r + 1,-v);
		}else
		{
			ll l,r;cin >> l >> r;
			cout << getsum(r) - getsum(l-1) << '\n';
		}
	}
}