0%

树状数组总结

树状数组总结

树状数组是一个类似于线段树的树状结构,它通过存储一定区间内的元素来达到快速插入、快速求和的效果。并且可以节省时间,节省空间,减少代码量,可谓是非常优秀的一个树形结构

方格中数字代表对应数组的第几个元素,下排是a数组,其上方的是e数组,最下的二进制则是对应编号的二进制表示.

可以观察到,树状数组把一个数组内的元素进行了一定的二分,并存储某些元素的和,使树的深度达到了logn,这样不论是对于查找还是插入都进行了极大的优化

每个数所指向的元素个数为1+它的二进制末尾0的个数我们把二进制中最后一个一出现的位置叫做lowbit,每个元素指向的下一个元素为x+lowbit(x),现在要修改整棵树就比较容易了。

  1. 累加操作

    void add(int x,int t)
    {
    while(x<=n){
    e[x]+=t;
    x=x+lowbit(x);
    }
    }

  1. 求和操作

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

其中,求和操作求的是1x个元素之和,要求ab个元素之和,只需: Ans=sum(b)-sum(a-1); 其中运用了两次查询,对于查询单个元素,还可以优化为一次: 借助data[x]=e[x]-(query(x-1)-query(LCA(x,x-1)))

int sum(x){
int ans=e[x];
int lca=x-lowbit(x);//求最近公共祖先
x--;
while(x!=lca){
ans-=e[x];
x-=e[x];
}
}

拓展操作:

  1. 区间修改、点查询

令e[i]为i元素与i-1元素的差值 那么区间[i,j]修改: e[i]+=d; e[j+1]-=d; 单个点的求值:data[i]=e[1]+e[2]+…+e[i];

  1. 找第k小的元素

e[i]数组存取i出现的次数(有时数据太大可以离散优化) 问题可以转化为求区间和为k所对应的下标 区间和为递增区间,用二分查找 如4 6 5 5 2 2 3 1,每个数作为下标,add一次 然后sum(i)求出的就是当前1~i区间的数字个数,并且数字有序,二分即可

  1. 向高维拓展

树状数组与线段树相比,还是比较方便向高维拓展的,只需加一重循环即可

void Change(int x,int y,int data){
While(x<=n){
int ty=y;
While(ty<=n){
e[x][ty]+=delta;
ty+=lowbit(y);
}
x+=lowbit(x);
}
}

树状数组 Ultra-QuickSort

题目(poj 2299) 请分析,对于一串数列,各个数字不相同,至少要交换多少次才能使该数列有序(从小到大)?

输入: 输入包含多组测试样例,每组测试样例都是先输入一个整数n<500000——序列的长度,以下n行每行包括一个整数 0 ≤ a[i]≤ 999,999,999,已输入的n为0作为输入的终止条件。

输出: 对于每一组样例,输出一个整数,表示至少要交换的次数。

输入样例: 5 9 1 0 5 4 3 1 2 3 0

输出样例: 6 0

很标准的一道题,先将所有元素取出排序,去重,作为离散优化二分的依据 依次从第一位开始向树状数组对应位置加值,add(find(x),1),并且同时算出当前比该元素大的值有多少,更新答案

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 500020
using namespace std;
int n,m,p,t[MAX],data[MAX];
long long e[MAX],s,ans;
int lowbit(int i){
return -i&i;
}
void add(int x,int p){
for(;x<=n;x+=lowbit(x))
e[x]+=p;
}

long long sum(int x){
for(s=0;x>0;x-=lowbit(x))
s+=e[x];
return s;
}

int Find(int s,int e,int aim){
while(s<=e){
int m=(s+e)>>1;
if(t[m]==aim) return m;
if(t[m]>aim) e=m-1;
else s=m+1;
}
}

int main(){
// freopen("in.txt","r",stdin);
while(~scanf("%d",&n)&&n){
memset(e,0,sizeof(e));
ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&data[i]);
t[i]=data[i];
}
sort(t+1,t+n+1);
m=unique(t+1,t+n)-t;
for(int i=1;i<=n;i++){
int f=Find(1,m,data[i]);//找离散优化对应元素
ans+=sum(n)-sum(f);//每次看比此数大的数有几个
add(f,1);//将此数加入
}
printf("%lld\n",ans);
}
return 0;
}

Poj3928 Ping Pong

题意: n(3 < = 20000)乒乓球运动员住在一个西大街(考虑街道作为一个线段)。每个球员都有一个独特的技能等级。为了提高他们的技能等级,他们经常互相竞争。如果两个球员想参加比赛,他们必须选择其他乒乓球运动员的裁判,并在裁判的房子举行比赛。因为某些原因,参赛者不能选择一个技能等级较高或低于他们两个级别的裁判。参赛者必须走到裁判的房子,因为他们是懒惰的,他们想使他们的总步行距离不超过他们的房子之间的距离。当然,所有的球员都住在不同的房子,他们的房子的位置都是不同的。如果裁判或任何两名选手是不同的,我们称之为两个不同的游戏。现在的问题是:有多少不同的游戏可以在这个乒乓街举行?

输入

The first lineof the input contains an integer T(1<=T<=20), indicating the number oftest cases, followed by T lines each of which describes a test case.

输入的第一行包含一个整数t(1 < =T < = 20),表示测试用例的数量,然后是T行,其中每一个描述了一个测试用例。

Every testcase consists of N + 1 integers. The first integer is N, the number of players.Then N distinct integers a1, a2 … aN follow, indicating the skill rank ofeach player, in the order of west to east. (1 <= ai <= 100000, i = 1 …N).

每一个测试用例都是由n个1个整数组成的。第一个整数是n,玩家的数量。然后,n个不同的整数A1、A2…一个跟随,指示每个玩家的技能等级,在西到东的顺序。(1 < = 100000,I = 1…n)。

Output 输出

For each testcase, output a single line contains an integer, the total number of differentgames. 对于每一个测试用例,输出一个单行包含一个整数,不同游戏的总数。

先把所有选手的能力值排序,然后加入能力值最低的选手,然后枚举所有可能成为裁判的选手,同时计算出这个裁判的左边和右边比裁判能力值大和小的值,ans+=(lmin*rmax+lmax*rmin);

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 20020
using namespace std;
struct node{
int id,data;
}peo[MAX];
long long e[MAX],t[MAX],data[MAX],lmin,rmin,lmax,rmax,ans;
int n;

bool cmp(node a,node b){
return a.data<b.data;
}
int lowbit(int i){
return -i&i;
}
void add(int x,int t){
for(;x<=n;x+=lowbit(x))
e[x]+=t;
}
long long sum(int x){
long long s=0;
for(;x>0;x-=lowbit(x))
s+=e[x];
return s;
}
int main(){
// freopen("in.txt","r",stdin);
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n); ans=0;
memset(e,0,sizeof(e));
for(int i=1;i<=n;i++){
scanf("%d",&peo[i].data);
peo[i].id=i;//位置
}
sort(peo+1,peo+1+n,cmp);//按能力排序
add(peo[1].id,1);//实力最小的选手
for(int i=2;i<=n-1;i++){
lmin=sum(peo[i].id-1);
lmax=peo[i].id-lmin-1;
rmin=sum(n)-sum(peo[i].id);
rmax=n-peo[i].id-rmin;
ans+=(lmin*rmax+lmax*rmin);
add(peo[i].id,1);
}
printf("%lld\n",ans);

}

return 0;
}

Stars 题目(POJ 2352) 天文学家常常检查星星地图,星星都有它的x,y坐标,星星的等级的是由下边星星数量和星星右边的星星数量决定。 例如,看看上面的星图。星星5的等级为3 (由星星1、2和4决定的)。星星2的等级为1(由星星1决定的)。在这张地图上0级的星星有一颗,1级的星星有两颗,2级的星星有一颗,3级的星星有一颗, 你要编写一个程序,计算每个等级的星星的数量。

输入: 第一行为星星的数量N((1<=N<=15000) 接下来N行,每行为星星的x,y坐标,用空格来分开(0<=X,Y<=32000),每一个点上只有一个星星,按Y的升序给出坐标,如果Y相同,则按照X的升序给出。

输出: 输出应该包含N行,每行一个数字。第一行0级星星的数量,第二行1级星星的数量等等,最后一行包含n – 1星星的数量。

输入样例: 5 1 1 5 1 7 1 3 3 5 5

输出样例: 1 2 1 1 0

乍一看像一道二位树状数组题,其实是一维的,因为数据本来就是按y的大小排序,添加每个点x之前先计算sum(x),这就是星星的等级,加入答案,继续直到循环结束

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 32020
using namespace std;
int e[MAX],cnt[MAX],n;

int lowbit(int i){
return -i&i;
}
void add(int x,int t){
for(;x<=MAX;x+=lowbit(x))
e[x]+=t;
}
int sum(int x){
int s=0;
for(;x>0;x-=lowbit(x))
s+=e[x];
return s;
}
int main(){
// freopen("in.txt","r",stdin);
int x,y;
while(~scanf("%d",&n)){
memset(e,0,sizeof(e));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
add(x+1,1);
cnt[sum(x+1)]++;
}
for(int i=1;i<=n;i++)
printf("%d\n",cnt[i]);
}
return 0;
}

Hdu 4031 attack 问题描述 今年是911的十周年,基地组织又想攻击美国了,美国有建设了一堵墙来保护自己,而基地组织有一个超级武器,每秒钟可以攻击连续的墙。而美国还有能量护盾来保护墙,每个能量护盾覆盖在一个单位长度的墙上,能抵挡攻击,但是每个能量护盾防御了一次攻击都需要T秒时间冷却下来,冷却期间,它不能抵挡攻击,比如该单位初盾牌抵挡了第k次攻击,那么它不能抵挡第k+1~(k+t-1)次攻击,过后,他们自动继续防御。 在战争中,知己知彼是非常重要的,因此指挥官想知道墙的某一部分被成功攻击了多少次,成功攻击就意味着盾牌没有防御到

输入

第一行T(<=20),表示测试数据组数 每组测试数据第一行:N,Q,T,分别表示墙的长度,Q次攻击或询问,T秒的冷却时间 接下来Q行,格式有两种: Attack si ti 攻击 si 到 ti 的墙. 1 ≤ si ≤ ti ≤ N Query p 询问p位置的墙:1 ≤ p ≤ N 1 ≤ N, Q ≤ 20000 1 ≤ t ≤ 50

输出

每组数据第一行: Case i: 接下来是所有询问的答案,每个询问答案一行

样例输入

2 3 7 2 Attack 1 2 Query 2 Attack 2 3 Query 2 Attack 1 3 Query 1 Query 3 9 7 3 Attack 5 5 Attack 4 6 Attack 3 7 Attack 2 8 Attack 1 9 Query 5 Query 3

样例输出

Case 1: 0 1 0 1 Case 2: 3 2

暂时没A,先放这里吧~

Poj 2985 The k-th Largest Group 题意 有N只猫,M个操作。操作种类如下: 0 a b:把a b猫所在的组合并 1 k: 第K大的组的大小是多少。 求第k大的数

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=200020;
int father[MAX],e[MAX];
int cnt[MAX];//存储有i只猫的集合数
int n,m,op,a,b,num;
int lowbit(int x){
return -x&x;
}
void add(int x,int t){
for(;x<=MAX;x+=lowbit(x))
e[x]+=t;
}
int Getfather(int p){
if(father[p]!=p)
father[p]=Getfather(father[p]);
return father[p];
}
int Get_kth(int k){
int ans,tot;//二分找第k小
ans=tot=0;
for(int i=20;i>=0;i--){
ans+=1<<i;//尝试
if(ans>=MAX||tot+e[ans]>=k)//看这次尝试是否超过范围
ans-=1<<i;//复原
else tot+=e[ans];//记录
}
return ans+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
father[i]=i;//并查集初始化
cnt[i]=1;//表示组内有i只猫的组数,开始只有一组
}num=n;//num个集合
add(1,n);
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op){
scanf("%d",&a);//第k大就是第num - k + 1小的
printf("%d\n",Get_kth(num-a+1));
}else{
scanf("%d%d",&a,&b);
a=Getfather(a); b=Getfather(b);//取父亲
if(a==b) continue;//本来属于一个集合
add(cnt[a],-1); add(cnt[b],-1);
add(cnt[a]+cnt[b],1);
cnt[b]=cnt[a]+cnt[b];
father[a]=b;
num--;
}
}
return 0;
}

Poj 1195 Mobile phones 题意: 给你一个矩阵(初始化为0)和一些操作: 1 x y a表示在arr[x][y]加上a 2 l b rt 表示求左上角为(l,b),右下角为(r,t)的矩阵的和。 高维树状数组即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=1200;
int e[MAX][MAX],n;
int lowbit(int i){
return -i&i;
}
int sum(int x,int y){
int ans=0;
while(x>0){
int ty=y;
while(ty>0){
ans+=e[x][ty];
ty-=lowbit(ty);
}
x-=lowbit(x);
}
return ans;
}

void add(int x,int y,int t){
while(x<=n){
int ty=y;
while(ty<=n){
e[x][ty]+=t;
ty+=lowbit(ty);
}
x+=lowbit(x);
}
}
int main(){
// freopen("in.txt","r",stdin);
int c,x,y,a,x1,x2,y1,y2;
scanf("%d%d",&c,&n);
while(~scanf("%d",&c)&&c!=3){
if(c==1){
scanf("%d%d%d",&x,&y,&a);
add(x+1,y+1,a);
}else{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans=sum(x2+1,y2+1)-sum(x1,y2+1)-sum(x2+1,y1)+sum(x1,y1);
printf("%d\n",ans);
}
}

return 0;
}