简单高效的排行榜算法——树状数组

字数统计: 2.8k阅读时长: 10 min

 2019/10/09 

0 问题场景

在互联网业务中，为了刺激玩家活跃度，通常都会制作榜单，让用户能够看到自己在榜单中的名次。用户要看到的内容是：新的分数排行是多少名，相比之前是前进了，还是后退了，具体前进后退的数值是多少。例如充值排行榜，游戏分排行榜，活跃度排行榜等。由于互联网用户基数大，有些平台参与排行的用户可以达到上千万。但是排行榜最重要的就是时效性，能够让用户越早看到排行更新越好。

对于庞大的榜单，每次其中一个元素更新，都要重新排序，即使用快速排序，对CPU运算的消耗都是巨大的，很容易造成卡顿。很多互联网业务都采用离线定时更新榜单的方案。例如每天凌晨4点的数据切片，离线排序更新，更新后展示最新的榜单。这种方案在程序性能和用户体验间做了折衷，既保证了每天更新，又不至于实时更新导致运算量太大，算不出来。

有没有更高的解决方案，可以实时查看用户排行变化呢？一个有序的排行榜，只是一个用户的数据发生变化，就要所有数据重新排序，能只做到部分排序吗？

对于这两个问题，可以利用一种高级的数据结构「树状数组」，再结合对排行榜的算法来实现。

1 排行榜实现及优化方案

我们先梳理下排行榜的通用实现方案，再查看下针对具体的步骤进行优化。
一个通用排行榜的实现方案步骤如下：

已经有一个排好序的排行榜；
当用户分数有更新时，保存用户老的排行榜名次和老的分数；
更新用户新的分数，并更新排行榜，获取新排行名次；
展示新老名次的差异，结束。

难点就在第二点，如何更新排行榜。最简单粗暴的想法是，更新排行榜中对应的分数，然后调用快速排序对数组再重新排序一次。快速排序时间复杂度是nlog(n)的，如果有1000万人参与，每次就要进行上亿次的比较。如果每秒有一千个玩家修改分数，要执行千亿次运算。对于排行榜系统的性能消耗是巨大的，做不到实时展示排行数据更新。

原先已经排好序的数组，只有一个元素的值发生了变化，其他元素的相对顺序是不用更改的。从这个角度来优化程序，能够做到快速实现排序优化。使用树状数组，能够做到修改和查询都是log(n),那么对于1000万人参与的榜单，比较次数最多只需要23次，一千个玩家每秒修改，只需要23000次比较。单进程都可以承受住。而且树状数组底层是构建在数组之上的，数据结构简单，容易持久化，能够方便地保存在共享内存中。当常驻进程重启时能够快速恢复。

说了树状数组这么多好处，这么适合排行榜业务的实现，下面我们来介绍下树状数组的原理，以及在排行榜业务中使用的方法。

2 树状数组实现排行榜

我们利用树状数组来实现排行榜功能，能够在Olog(N)的复杂度实现查询和修改功能。下面先介绍树状数组的原理，再介绍如何利用树状数组来实现排行榜。由于涉及到学习算法，还有应用。本节的两个内容需要对照查看才能理解，建议对下面两小节的内容，先概览熟悉基本概念，再逐渐研究细节。并没有严格的先后顺序之分。

2.1 树状数组原理

树状数组（Binary Indexed Tree），又以其发明者命名为Fenwick树。可以在O(logn)时间内得到数组任意前缀和，并能够在O(log(n))时间内支持动态单点的值的修改。空间复杂度是O(n)。

所有的正整数，都可以表示为2的幂和。 $N=\sum_{i=1}^m2^{ki} $ ,ki为二进制表示时，为1位的位置。

例如$34=2^1+2^6;12 = 2^2+2^3$;

我们设一个整数数组元素个数为N，数组名为A，包含元素为$A_{j}(1<=j<=N)$

对于一个整数i，lowbit(i)表示i的二进制最后一个位置1，所代表的值。（例如lowbit（12）= 4，lowbit（34）=2）

构造树状数组 $BIT_{i} = \sum_{j=i-lowbit(i)+1}^{i}A_{j}$

BIT[i]=A[i-lowbit(i)+1] + A[i-lowbit(i)+2] + ... + A[i]

所表示的数学意义为，下标为i的树状数组元素，为原数组A[i]往前lowbit(i)个元素的和（包括A[i])。

对于树状数组元素BIT[i]，可以画一棵树表示，树中的父节点表示的区间和，覆盖子节点表示的区间和。

下图为i=8时画出的树。

树状数组是在数组上建立的一种树形关系结构。

以上图为例，A数组是原始存储数据的数组，有8个元素。C数组是按照每个下标覆盖2次幂范围得到的新的子序列和的数组。

BIT1 = A1 （1的二进制表示为1，有0个0，覆盖1个元素）

BIT2 = A1 + A2（2的二进制表示为10，有1个0，覆盖2个元素）

BIT3 = A3（3的二进制表示为11，有0个0，覆盖1个元素）

BIT4 = A1 + A2 + A3 + A4（4的二进制表示为100，有2个0，覆盖4个元素）

BIT5 = A5（5的二进制表示为101，有0个0，覆盖1个元素）

BIT6 = A5 + A6（6的二进制表示为110，有1个0，覆盖2个元素）

BIT7 = A7（7的二进制表示为111，有0个0，覆盖1个元素）

BIT8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8（8的二进制表示为1000，有3个0，覆盖8个元素）

有了树状数组BIT[i]，我们就可以实现求原数组A[i]的前缀和，还有A[i]中单个元素修改时快速更新BIT[i]数组的功能。

一、求原数组A的前缀和

假设求原数组A的前i个元素的和Sum[i]，对于整数区间[1,i],可以表示为两个区间[1, i-lowbit(i)],[1-lowbit(i), i]。

如果设j=i-lowbit(i)，那么j<=i并且Sum[0] = 0，则Sum[i] = Sum[j] + BIT[i]；之后再逐步求解Sum[j]，直到递推到Sum[0] = 0，便计算出前缀和Sum[i]。

二、原数组某个元素A[i]修改，同步修改树状数组BIT

当某个元素A[i]修改时，所有包含A[i]的树状数组元素BIT[j]都要进行相应的修改。

对于A[i]，BIT[i]肯定包含A[i]的和。再根据上面的树形结构，

$BIT_{i_{k+1}} = BIT_{i_{k}} + lowbit(i_{k}) 其中 (i_{0}=i, i_{k+1}<=N)$

2.2 代码实现

根据上一小节的分析，可以用代码实现树状数组。
对于求lowbit(n),可以用n&(n^(n-1))得到，由于在C++中用补码表示负数，可以写为n&(-n)。用函数封装为

int lowbit(int x)
{
	return x & (-x);
}

求数组A的前i项和为

int sum(int i)//求前i项和 
{ 
    int s=0; 
    while(i>0) 
    { 
        s+=BIT[i]; 
        i-=lowbit(i); 
    } 
    return s; 
}

修改原数组A[i]元素，增加val值

void add(int i,int val) 
{ 
    while(i<=n) 
    { 
        BIT[i]+=val; 
        i+=lowbit(i);  
    } 
}

2.3 树状数组优化排行榜

如何使用树状数组来实现排行榜的需求呢？要经过一些转化。

我们把要排行的分数划定一个区间范围。假设分数都是整数，最大值MAX_SCORE为1,000,000分。

则原始数组A[i]表示具有分数为i的值的用户数量，然后求出BIT[i]数组。假设一个人的分数为j，则排名为BIT[MAX_SCORE]-BIT[j-1]。

利用上小节的代码很容易就实现了。

排行榜封装的代码如下

const int MAX_SCORE = 1000000;
int BIT[MAX_SCORE + 1]={0};//初始时所有分数的人数都是0
while(true)
{
    int uid, newScore, oldScore;
    GetUserInfoReq(&uid, &newScore, &oldScore);//假设收到请求，获得uid用户的最新分数为newscore,上次更新分数为oldscore;
    int oldRank = sum(MAX_SCORE)-sum(oldScore)+1;//查询旧排名
    //更新为新排名
	add(oldScore, -1);//先给旧分数的人数减一
	add(newScore,  1);//再给新分数的人数加一
	int newRank = sum(MAX_SCORE)-sum(newScore)+1;
	//返回用户新排名newRank，和老排名oldRank供前端展示
    SetUserInfoRsp(uid, newScore, newRank, oldScore, oldRank);
}