LiaN

是一只废物捏

0%

【题解】树状数组和线段树

发表于 更新于 分类于 本文字数： 6.9k 阅读时长 ≈ 6 分钟
  • 主要内容
    • 它俩下标都从1开始
    • 树状数组：
      • 动态快速求前缀和，单点修改（某个位置上加上一个数），区间查询（前缀和）
      • 时间复杂度：O(logN)
      • lowbit()，add(int x,int v)：原数组的下标x的值加上v，query(int x)：查询原数组下标1到x的前缀和
    • 线段树：
      • 能处理的范围更大，包含树状数组，比树状数组慢；单点修改，区间查询
      • 一个长度为n的区间，线段树节点总个数小于等于4n；定义每个节点（左边界、右边界、某个属性）
      • pushup：用子结点信息 更新 当前节点的信息；build：在一段区间上初始化线段树
        ；modify：修改；query：查询

树状数组

  • 可以动态地、快速 求前缀和 ； logN
    • 给某个位置的数 加上 一个数（单点修改）
    • 求某一个前缀和 （区间查询）
  • 它只能解上述单点修改和区间查询问题，其他问题要转换成这种类型的才可以解
  • 数组下标从1开始
  • 树状数组相当于一个辅助数组，不要把树状数组和原数组混淆，我们要求的是原数组的前缀和 要求的是在原数组加上某个数，然后借用一个树状数组进行操作，而不是在原数组上操作

下图来源：AcWing 1264. 动态求连续区间和 - AcWing

  • lowbit(x) = x & -x = 2^k：其中k：x末尾0的个数

AcWing1264 动态求连续区间和（树状数组求解）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using  namespace std;

const int N=100010;
//a原数组，tr树状数组 
int a[N],tr[N];
int n,m;

//返回值= 2^k，其中k等于x二进制末尾0的个数 
int lowbit(int x){
	return x&(-x);
}

//在原数组第x个数上加上v ，对应的树状数组发生改变
void add(int x,int v){
	for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}

//利用树状数组，返回原数组第1个数加到第x个数的前缀和 
int query(int x){
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
	return res;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) add(i,a[i]);
	while(m--){
		int k,x,y;
		scanf("%d%d%d",&k,&x,&y);
		if(k==0){
			printf("%d\n",query(y)-query(x-1));
		}else{
			add(x,y);
		}
	}
}

AcWing1265 数星星

题意

1265. 数星星 - AcWing题库

概括：给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

思路

  • 动态输入每个点的坐标的时候，对于当前刚输入的点的坐标，它的左下方的坐标存在的星星数量刚好是 当前输入点x方向 左方的所有坐标存在的星星数量
  • 因此，只需要求出当前x坐标的左边，即：从坐标1到x上的星星 个数总和即可；即可转换成求前缀和；
  • 由于每输入一个星星坐标，对于前缀和数组，该星星后面的前缀和数组的值都会+1，所以可以看成一个动态区间求前缀和的 问题，因此完全可以转换成树状数组来求解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int N=32005;
int n;
int tr[N],a[N];
//a[i]:等级为i的星星的个数 
//假设树状数组tr[N]所处理的原数组是b[N]，b[i]表示横坐标为i的星星的数量 
int lowbit(int x){
	return x&-x;
}
int add(int x,int v){
	for(int i=x;i<=N;i+=lowbit(i)) tr[i]+=v;
}
//查询原数组从坐标1到x的前缀和：即是位于坐标1到x上所有星星的数量
int query(int x){
	int ans=0;
	for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
	return ans;
}
int main(){
	scanf("%d",&n);
	int temp_n=n;
	while(temp_n--){
		int x,y;scanf("%d%d",&x,&y),++x,++y;
		add(x,1);
		int tot=0;
		tot=query(x);
		a[tot]++;
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",a[i]);
}

AcWing1215 小朋友排队

题意

给定一个数组，要求从小到大排序，每次只能交换相邻位置。定义一个sum

当原数组的第i个数总共被交换了k次，sum+=(1+k)*k/2

求最小的sum

思路

  • 从小到大，交换相邻：冒泡排序，但是数据范围1≤n≤100000，冒泡里面再加一层for的话会爆

    n≤100000推出算法复杂度最多是O(nlogn) => 截止写这个题解之前本fw学过的可能有各种sort，线段树、树状数组、二分…..

  • 比如给定一个数组：3 4 2 1 4；对于2前面的数来说，只要比2大，必然会被交换一次；对于2后面的数来说，只要比2小，也必然会被交换依次；

  • 可以推出，对于第i个数，被交换的次数就是k1+k2；

    • 故关键在于，对于第i个数，求出它前面比它大的数的个数k1 ,求出它后面比它小的数的个数k2

    • 针对一个k1或者k2会被计算两次，故，求总的交换次数是所有k之和除以2

  • 假设存在一个数组b[i]（树状数组的原数组）：存放身高==i的小朋友个数，（关键在于是：个数！！）

  • 对于k1：对于一组已知的小朋友的身高，我们可以一个个处理，比如，当处理到第x个小朋友的身高时（此时并不理会x后面的小朋友的身高），在此前，将前面的x-1小朋友的身高就可以存在b[i]（身高=i 的个数） 中，这个b[i]其实用一个树状数组来维护（因此不需要表示出b这个数组）

    • query(int a)则表示求出 身高在 1到a 之间的小朋友的个数
    • 若要求前面x-1个小朋友身高大于第x个小朋友身高(假设为hh）的个数，即query(N)-query(hh-1)
    • 即是当前，身高在1到N之间小朋友的个数 减去 身高≤hh的小朋友个数

  • 同理可得k2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int n;
int a[N],tr[N],c[N]; 
//c[i],第i个小朋友被交换的次数 
//a[i]：输入的数组，第i个小朋友的身高 
//假设树状数组tr[i]处理的原数组b[i],b[i]表示：当前身高==i的小朋友个数 
int lowbit(int x){
	return x&-x;
}
int add(int x,int v){
	for(int i=x;i<=N;i+=lowbit(i)) tr[i]+=v;
}
//身高在1到x之间的小朋友个数 
int query(int x){
	int ans=0;
	for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
	return ans;
}
int main(){
	scanf("%d",&n);
	//一旦要使用树状数组，要保证树状数组的原数组下标从1开始 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]++;
	//对于每个a[i],先找它前面比它大的数的个数，
	for(int i=1;i<=n;i++){
		//动态地处理,和上道数星星的题类似
		 add(a[i],1);
		 c[i]=query(N)-query(a[i]); 
	}
	//记得清空一次数组 
	memset(tr,0,sizeof tr);
	//对于每个a[i],找它后面比它小的数的个数 
	for(int i=n;i>=1;i--){
		add(a[i],1);
		c[i]+=query(a[i]-1); 
	}
	LL ans=0;
	for(int i=1;i<=n;i++){
		ans+=(LL(1+c[i])*c[i])/2;
	}
	printf("%lld\n",ans);
}

线段树

  • 线段树能处理的范围包含树状数组
  • 代码短、常数小
  • 求区间最大值，面积，长度
  • 对于一个长度为n的区间，线段树节点总个数小于等于4n
  • 存储到数组里面，对于下标x
    • 父节点 x/2 (下取整)，即是 x>>1
    • 左子结点：2x ,即是 x<<1
    • 右子结点：2x+1，即是 x<<1|1

  • 比如对于上述维护总和的操作有
    • 单点修改
    • 区间查询 O(logN)
1
2
3
4
//pushup:用子结点信息 更新 当前节点的信息；可能有时候比较简单，直接写到别的函数内部去
//build：在一段区间上初始化线段树
//modify：修改操作
//query：查询操作

AcWing1264 动态求连续区间和（线段树求解）

题意

给定一个数组，多个操作：修改某个元素，求子数组的连续和

思路

设计区间的单点修改和查询，考虑线段树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,m;
int w[N];
struct Node{
	int l,r;//左右边界 
	int sum;
}tr[N*4];

//更新当前节点u的信息 
void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

//u当前节点编号 l r左右边界 
void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,w[r]}; 
	else{
		tr[u]={l,r};
		int mid=l+r>>1;//加法的优先级高于移位 
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
//从u根节点编号开始查，l r要查询区间的左右边界 
int query(int u,int l,int r){
	//lr已经将整个该节点包含在该lr区间内 
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;

	//否则，计算下当前节点内的中点 
	int mid=tr[u].l+tr[u].r>>1;
	int sum=0;
	//如果区间左边界在mid的左边,查询左子节点，注意这里都还是lr区间 
	if(l<=mid)  sum=query(u<<1,l,r); 
	//如果区间有边界在mid的右边 
	if(r>mid)  sum+=query(u<<1|1,l,r);
	return sum; 
}
//u当前的根节点编号 在x的位置加上v 
void modify(int u,int x,int v){
	if(tr[u].l==tr[u].r) tr[u].sum+=v;
	else{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid) modify(u<<1,x,v);
		else modify(u<<1|1,x,v);
		pushup(u);//上面对u的子结点进行操作完毕后要更新u
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i];
	build(1,1,n);//记得要先建立线段树
	int k,a,b;
	while(m--){
		cin>>k>>a>>b;
		if(k==0) cout<<query(1,a,b)<<endl;
		else modify(1,a,b);
	}
	return 0;
}

AcWing1270 数列区间求最大值

题意

一个数组，M个询问，每次查询第X到Y个数字的这个区间中的最大值

思路

  • 因为1≤N≤1e5，1≤M≤1e6，如果直接暴力，有M个询问，对于每个询问，遍历一遍x到y之间的数据，双重循环显然会爆，
  • 但它涉及到对一个区间的查询，且根据数据范围可知时间复杂度最多为nlogn，所以考虑使用线段树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int w[N];
struct Node{
	int l,r;
	int zd;
}tr[4*N];

void pushup(int u){
	tr[u].zd=max(tr[u<<1].zd,tr[u<<1|1].zd);
}
void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,w[r]};
	else{
		tr[u]={l,r};//当前节点u的左右边界是lr ！！
		int mid=l+r>>1;//建树的过程
        //建立左右子树
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        //更新节点
		pushup(u);
	}
}
//从节点u开始，查询边界lr 
int query(int u,int l,int r){
	int maxnum=INT_MIN;
	//如果节点u包含在边界lr里面，意思是lr的范围比u的范围还大
	//u从1开始，等价于返回值整个数组的最大值 
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].zd;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) maxnum=query(u<<1,l,r);
	if(mid<r) maxnum=max(maxnum,query(u<<1|1,l,r));
	return maxnum;	
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	build(1,1,n);
	int x,y;
	while(m--){
		scanf("%d%d",&x,&y);
		printf("%d\n",query(1,x,y));
	}
}