「Day 7—离散化 & 树状数组 & 线段树」

离散化

定义

离散化本质是一种哈希，是一种用来处理数据的方法。
1.创建原数组的副本。
2.将副本中的值从小到大排序。
3.将排序好的副本去重。
4.查找原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值。

B3694 数列离散化

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
int n;
int T; 
int a[MAXN],tmp[MAXN];

void lsh(){
	for(int i = 1;i <= n;i ++){
		//复制一个数组用来去重用
		tmp[i] = a[i];
	}
	sort(tmp + 1,tmp + n + 1);
	//去重
	int len = unique(tmp + 1,tmp + n + 1) - tmp - 1;
	for(int i = 1;i <= n;i ++){
		//离散
		a[i] = lower_bound(tmp + 1,tmp + len + 1,a[i]) - tmp;
	}
	for(int i = 1;i <= n;i ++){
		cout << a[i] << " ";
	}
	cout << "\n";
}

int main(){
	cin >> T;
	while(T --){
		cin >> n;
		for(int i = 1;i <= n;i ++){
			cin >> a[i];
		}
		lsh();
	}
	return 0;
}

树状数组

定义

树状数组是一种支持 单点修改 和 区间查询 的数据结构。
下图是一个树状数组的示意图，

具体的看代码

P3374 【模板】树状数组 1

代码

#include<iostream>
using namespace std;

const int MAXN = 5 * 1e5 + 5;
int n,m;
int sum[MAXN];

int lowbit(int x) {
  // x 的二进制中，最低位的 1 以及后面所有 0 组成的数。
  // lowbit(0b01011000) == 0b00001000
  //          ~~~~^~~~
  // lowbit(0b01110010) == 0b00000010
  //          ~~~~~~^~
  return x & -x;
}
//将x加上k
void add(int x,int k){
	while(x <= n) sum[x] += k,x += lowbit(x);
}

//计算从1 ~ x的和
int f(int x){
	int ans = 0;
	while(x) ans += sum[x],x -= lowbit(x);
	return ans;
}

int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		add(i,x);
	}
	for(int i = 1;i <= m;i ++){
		int op,x,y;
		cin >> op >> x >> y;
		if(op == 1) add(x,y);
		else cout << f(y) - f(x - 1) << "\n";
	}
}

P3368 【模板】树状数组 2

代码

#include<iostream>
using namespace std;

const int MAXN = 5 * 1e5 + 5;
int n,m;
int sum[MAXN],a[MAXN];

int lowbit(int x){
	return x&-x;
}
void add(int x,int k){
	while(x <= n) sum[x] += k,x += lowbit(x);
}
int f(int x){
	int ans = 0;
	while(x) ans += sum[x],x -= lowbit(x);
	return ans;
}

int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i = 1;i <= m;i ++){
		int op,x,y,k;
		cin >> op >> x;
		if(op == 1){
			cin >> y >> k;
			//运用差分的思想 差分数组在x处+k,在y+1处-k就完成了对x~y的区间加k问题
			add(x,k);
			add(y + 1,- k);
		}
		else cout << a[x] + f(x) << "\n";
	}
}

线段树

定义

线段树是为了维护区间信息的一种数据结构，线段树可以在 \(O(\log N)\) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

P3372 【模板】线段树 1

思路

我们用递归建树来完成，具体的看代码。

代码

定义结构体

struct node{
//l是左子树的节点编号，r是右子树的节点编号，sum为当前节点的区间和（l~r），add是当前节点的懒惰标记。
	int l,r,sum,add;
}t[MAXN * 4]; 

上传操作

void pushup(int p){
//当前节点的区间和=左子树的区间和+右子树的区间和
	t[p].sum = t[lc].sum + t[rc].sum;
	return;
}

下传操作

void pushdown(int p){
//判断当前节点是否有懒惰标记，如果有就下放给其左右子树
	if(t[p].add){
		//下放左子树
		t[lc].add += t[p].add;
		//下放右子树
		t[rc].add += t[p].add;
		//同时也要将懒惰标记的数值下放给左右子树的区间值
		//左子树的区间+区间元素数量*懒惰标记
		t[lc].sum += t[p].add * (t[lc].r - t[lc].l + 1);
		//右子树的区间+区间元素数量*懒惰标记
		t[rc].sum += t[p].add * (t[rc].r - t[rc].l + 1);
		//下放完成后将根节点的懒惰标记清0
		t[p].add = 0;
	}
}

建树

void build(int p,int l,int r){
	//我们采用递归建树的方式
 	t[p] = {l,r,0,0};
	//l = r说明这是一个叶子结点，则区间值也就是（l~r）的值为其本身的值x[l]或x[r]，这个无所谓
 	if(l == r){
 		t[p].sum = x[l];
 		return;
 	}
	//位运算避免溢出，等同于(l + r) / 2 或者 (l + r) >> 1
	int mid = (l & r) + ((l ^ r) >> 1);
	//以lc（p << 1）为左子树的根建立以l为区间左端点，mid为区间右端点的左子树
	build(lc,l,mid);
	//以rc (p << 1 | 1) 为右子树的根建立以mid+1为区间左端点，r为区间右端点的右子树
	build(rc,mid + 1,r);
	//进行上传操作，上传的原因是因为既然左子树和右子树都建立了，且其区间值也计算完毕，那么就应该利用左右子树向上传递其区间值。
	//例如p为【1~2】的区间，左子树lc【1~1】的值为4，右子树rc【2~2】的值为6.
	//那么p的值此时为lc.sum + rc.sum，即4 + 6 = 10,。
	pushup(p);
}

区间查询

int query(int p,int l,int r){
	//如果当前节点 p 代表的区间 [t[p].l, t[p].r] 完全在我们查询的区间 [l, r] 之内
	//（即 l <= t[p].l 且 t[p].r <= r），那么我们可以直接返回这个节点的和 t[p].sum，而不需要进一步递归地查询子节点。
	if(l <= t[p].l && t[p].r <= r) return t[p].sum;
	//依旧是位运算，求的是当前节点p的区间中点
	int mid = (t[p].l & t[p].r) + ((t[p].l ^ t[p].r) >> 1);
	//下传一下懒惰标记，防止没有下传导致查询出错
	pushdown(p);
	int sum = 0;
	//如果要查的区间的左端点比mid小，说明还要向左子树继续递归求值
	if(l <= mid){
		sum += query(lc,l,r);
	}
	//如果要查的区间的右端点比mid大，说明还要向右子树继续递归求值
	if(r > mid){
		sum += query(rc,l,r);
	}
	//最后返回左右子树的值之和
	return sum;
}

区间修改

void change(int p,int l,int r,int k){
	//如果区间刚好对上了，那么就让当前的节点的区间值+区间元素*k
	if(l <= t[p].l && t[p].r <= r){
		t[p].sum += (t[p].r - t[p].l + 1) * k;
		//懒惰标记，方便下传
		t[p].add += k;
		return;
	}
	//如果没对上说明还是有左右子树需要继续修改
	//又双叒是位运算，求的是当前节点p的区间中点
	int mid = (t[p].l & t[p].r) + ((t[p].l ^ t[p].r) >> 1);
	//下传懒惰标记，防止在修改子树是区间值不对
	pushdown(p);
	//如果要修改的区间的左端点比mid小，说明还要向左子树继续递归修改
	if(l <= mid) change(lc,l,r,k);
	//如果要修改的区间的右端点比mid大，说明还要向右子树继续递归修改
	if(r > mid) change(rc,l,r,k);
	//修改完别忘了去给p更新值
	pushup(p);
}

完整代码

#include<iostream>
#define lc p << 1
#define rc p << 1 | 1
#define int long long
using namespace std;

const int MAXN = 1e5 + 5;
int n,m,x[MAXN];
struct node{
	int l,r,sum,add;
}t[MAXN * 4]; 
//上传 
void pushup(int p){
	t[p].sum = t[lc].sum + t[rc].sum;
	return;
}
//下传 
void pushdown(int p){
	if(t[p].add){
		t[lc].add += t[p].add;
		t[rc].add += t[p].add;
		t[lc].sum += t[p].add * (t[lc].r - t[lc].l + 1);
		t[rc].sum += t[p].add * (t[rc].r - t[rc].l + 1);
		t[p].add = 0;
	}
}
//建树 
void build(int p,int l,int r){
// 	t[p] = {l,r,x[l],0};
 	t[p] = {l,r,0,0};
 	if(l == r){
 		t[p].sum = x[r];
 		return;
 	}
	int mid = (l & r) + ((l ^ r) >> 1);
	build(lc,l,mid);
	build(rc,mid + 1,r);
	pushup(p);
}
int query(int p,int l,int r){
	if(l <= t[p].l && t[p].r <= r) return t[p].sum;
	int mid = (t[p].l & t[p].r) + ((t[p].l ^ t[p].r) >> 1);
// 	int mid = (t[p].l + t[p].r) / 2;
	pushdown(p);
	int sum = 0;
	if(l <= mid){
		sum += query(lc,l,r);
	}
	if(r > mid){
		sum += query(rc,l,r);
	}
	return sum;
}
void change(int p,int l,int r,int k){
	if(l <= t[p].l && t[p].r <= r){
		t[p].sum += (t[p].r - t[p].l + 1) * k;
		t[p].add += k;
		return;
	}
	int mid = (t[p].l & t[p].r) + ((t[p].l ^ t[p].r) >> 1);
	pushdown(p);
	if(l <= mid) change(lc,l,r,k);
	if(r > mid) change(rc,l,r,k);
	pushup(p);
}

signed main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		cin >> x[i];
	}
	build(1,1,n);
	for(int i = 1;i <= m;i ++){
		int op,x,y,k;
		cin >> op >> x >> y;
		if(op == 1){
			cin >> k;
			change(1,x,y,k); 
		}
		else{
			cout << query(1,x,y) << "\n";
		}
	} 
	return 0;
}