当前位置：首页 > news >正文

数据结构＜1＞——树状数组

news 来源：原创 2024/5/20 12:17:11

树状数组，也叫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 二进制表示中第一个 1 是 x 最低位的 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(你会挂的很惨)，看懂了自己写一遍