数据结构<1>——树状数组

发布时间:2024年01月24日

树状数组,也叫Fenwick Tree和BIT(Binary Indexed Tree),是一种支持单点修改区间查询的,代码量小的数据结构。

那神马是单点修改和区间查询?我们来看一道题。

洛谷P3374(模板): 在本题中,单点修改就是将某一个数加上x的操作,区间查询就是求出某区间每一个数的和的操作,这下明白了吧。

下面来解释一下树状数组的工作原理。先看一张(来源于OI-Wiki)

Tips:别找了,点一下"图"那个字就有了。

我们发现,树状数组总能将一段前缀拆成不多于log n段区间,使得这几段区间的信息是已知的。因此,我们只用合并这些区间的信息,就可以得到答案。因此,时间复杂度从\Theta (n)变成\Theta (log n),效率大大提高。

管辖区间

我们观察刚刚的发现,每个c_{i}相当于一个小leader,掌管自己的范围。那这个范围是多少呢?我们规定c_{i}管辖的区间长度为2^{k},其中k为x的二进制表示中,最低位的1所在的二进制位数。而2^{k}为x的二进制表示中,最低位的1以及后面所有0组成的数。即c_{x}管辖的区间是[x-lowbit(x)+1,x]注意:lowbit(x)表示这个1和后面所有0组成的2^{k}

下面附上OI-Wiki中对lowbit(x)的原理的解释(其实是我不会解释)

x 的二进制所有位全部取反,再加 1,就可以得到 -x 的二进制编码。例如, 的二进制编码是 110,全部取反后得到 001,加 1 得到 010

设原先 x 的二进制编码是 (...)10...00,全部取反后得到 [...]01...11,加 1 后得到 [...]10...00,也就是 -x 的二进制编码了。这里 x 二进制表示中第一个 1x 最低位的 1

(...)[...] 中省略号的每一位分别相反,所以 x & -x = (...)10...00 & [...]10...00 = 10...00,得到的结果就是 lowbit

//lowbit的实现
int lowbit(int x){
	return x&(-x);
}

lowbit可以说是一个很经典的二进制运算了。

区间查询

经过上面的分析,我们可以知道回答区间查询的步骤了:

·c_{x}往前跳,一直让x-lowbit(x)就行了。

· 如果x=0就结束循环

· 将跑到的c_{x}累加

实现如下↓:

int get_sum(int x){
	int sum=0;
	while(x>0){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

单点修改

也很简单。

· 先修改c_{x}

· 然后一直让让x+lowbit(x)

· 如果x=n就结束循环

实现如下↓:

void modify(int x,int y){
	while(x<=n){
		c[x]+=y;
		x+=lowbit(x);
	}
}

洛谷P3374(模板):

那这题就很easy啦~

#include <bits/stdc++.h>
using namespace std;
int c[maxn];
int n,m;
int lowbit(int x){
	return x&(-x);
}
void modify(int x,int y){
	while(x<=n){
		c[x]+=y;
		x+=lowbit(x);
	}
}
int get_sum(int x){
	int res=0;
	while(x>0){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
  		int x;
  		cin>>x;
  		modify(i,x);
	}
	for(int i=1;i<=m;i++){
		int op,x,y;
  		cin>>op>>x>>y;
  		if(op==1)
   			modify(x,y);
  		if(op==2)
   			cout<<get_sum(y)-get_sum(x-1)<<endl;
	}
	return 0;
}

别走啊,这不得在找几题练练?

逆序对:

基础题。现在按照序列从左到右将数据的值对应的位置的数加一,代表又有一个数出现。因此,在循环到第i项时,前i-1项已经加入到树状数组内了,树状数组内比a_{i}大的都会与a_{i}构成逆序对,因为它们一定出现的更早,所以产生的逆序对数量为i-query(a_{i})。要注意的是,我们需要进行离散化,因为根据a_{i}建树确实不够。然后就是代码部分啦。

#include <bits/stdc++.h>
using namespace std;
pair<long long,long long> a[maxn];
long long b[maxn],c[maxn];
int n;
int lowbit(int x){
	return x&(-x);
}
void modify(int x){
	while(x<=n){
		c[x]++;
		x+=lowbit(x);
	}
}
int get_sum(int x){
	int sum=0;
	while(x>0){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].first;
		a[i].second=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		b[a[i].second]=i;
	long long ans=0;
	for(int i=n;i;i--){
		ans+=get_sum(b[i]);
		modify(b[i]);
	}
	cout<<ans<<endl;
	return 0;
}

当然,用归并也是Ok的。

火柴排队:

一道非常非常经典的题目。我们乍一看,就是让我们最小化\sum_{i=1}^{n} (a_{i}-b_{i})^{2},也就是最小化a_{i}-b_{i},也就是a序列第k大的元素必须和序列b中第k大的元素的位置必须一样。OK,那我们把a,b离散化,问题变成了b序列要交换几次可以令其等于a。我们令id_{a_{i}}=b_{i},相当于以a_{i}为关键字对序列b_{i}排序,如果a和b一样,那么q_{i}=i。那么我们需要让q升序排列。问题又变成,将原本乱的 q序列升序排列的最少交换次数。

诶,这不就是逆序对吗?

用树状数组或归并即可。这里给归并的代码,树状数组的参考上面P1908的代码。

#include <bits/stdc++.h>
using namespace std;
int a[maxn],b[maxn];
int c[maxn],d[maxn];
int num1[maxn],num2[maxn];
int calc[maxn];
long long ans=0;
int tmp[maxn];
void msort(int l,int r){
	if(l==r)
		return;
	int mid=(l+r)>>1;
	msort(l,mid);
	msort(mid+1,r);
	int i=l,j=mid+1;
	int k=l;
	while(i<=mid && j<=r){
		if(a[i]<=a[j])
			tmp[k++]=a[i++];
		else{
			tmp[k++]=a[j++];
			ans+=mid-i+1;
			ans%=MOD;
		}
	}
	while(i<=mid)
		tmp[k++]=a[i++];
	while(j<=r)
		tmp[k++]=a[j++];
	for(int i=l;i<=r;i++)
		a[i]=tmp[i];
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
		d[i]=b[i];
	}
	sort(d+1,d+n+1);
	for(int i=1;i<=n;i++)
		num1[d[i]]=i;
	sort(c+1,c+n+1);
	for(int i=1;i<=n;i++)
		num2[c[i]]=i;
	for(int i=1;i<=n;i++)
		calc[num1[b[i]]]=i;
	for(int i=1;i<=n;i++)
		a[i]=calc[num2[a[i]]];
	msort(1,n);
	cout<<ans%MOD<<endl;
	return 0;
}

别忘了取模哦。

The Last Problem:ABC157E

此题一看就是树状数组。但是由于有26个字母,我们要建26个树状数组,每一个存放该字母出现的位置。这样,在询问的时候,直接查询每一个树状数组的[l,r]的和,如果这个和>0,那么就把 ans加1,最后输出即可。

#include <bits/stdc++.h>
using namespace std;
int c[26][500005];
int lowbit(int x){
	return x&(-x);
}
void update(int c[],int x,int val){
	while(x<=500000){
		c[x]+=val;
		x+=lowbit(x);
	}
}
int getsum(int c[],int x){
    int sum=0;
    while(x>0){
    	sum+=c[x];
    	x-=lowbit(x);
	}
    return sum;
}
int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    str=' '+str;
    for(int i=1;i<=n;i++)
		update(c[str[i]-'a'],i,1);
	int q;
    cin>>q;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            char ch;
            cin>>x>>ch;
            update(c[str[x]-'a'],x,-1);
            update(c[ch-'a'],x,1);
            str[x]=ch;
        }
        if(op==2){
            int l,r;
            cin>>l>>r;
            int ans=0;
            for(int i=0;i<26;i++){
				if(getsum(c[i],r)-getsum(c[i],l-1))
					ans++;
			}
            cout<<ans<<endl;
        }
    }
    return 0;
}

Ok,以上就是本期的全部内容了。我们下期再见!

温馨提示:本期的所有代码都有问题,请不要无脑Ctrl C+Ctrl V(你会挂的很惨),看懂了自己写一遍

文章来源:https://blog.csdn.net/seanli1008/article/details/135714371
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。