树状数组小结

发表于 | 分类于 | 评论数：

介绍常用的数据结构之树状数组

最近做了几道树状数组的题目，借此想巩固一下已学到的知识.
这里推荐给大家一份翻译过来的讲树状数组的资料，非常值得一看.
树状数组的代码比较简单，也不易出错，网上有许多介绍这方面的资料，在这里就不在赘述。下面贴上我用的代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void update(int idx, int val)
{
    while(idx <= maxn)
    {
        c[idx] += val;
        idx += idx & -idx;
    }
}
int getsum(int idx)
{
    int sum = 0;
    while(idx > 0)
    {
        sum += c[idx];
        idx -= idx & -idx;
    }
    return sum;
}

注意：树状数组只能处理大于0的下标，如果有0的话上述函数会陷入死循环.

01 区间求和类问题

很显然，树状数组比较常用的功能就是维护区间和.当然，线段树也可以完成，但是编码比较复杂，稍不容易就出错.

(1)单点修改，区间查询

树状数组的基本功能，不做过多解释.注意一点:求和可能会爆int.

(2)区间修改，单点查询

有趣的是，这种问题树状数组的代码并没有改动，只是意义发生了变化.

如上图，a[]数组是原数组.现在有一操作，修改[l,r]之间的元素，使之区间元素全部加1，但是树状数组更新的只能是单点，那应该怎么办呢？
我们把区间的第一个元素加1之后，该元素之后的所有的元素都加1，我们再在区间后的第一个元素减一，这样该元素之后所有的元素都减一，相当于之后的元素没有受到区间修改的影响.这样我们在做getsum的操作的时候，b[i] = getsum(i);此时b[]数组就是修改后各个元素的值.
即：区间修改，修改区间的第一个元素，区间后的第一个元素；单点查询求的是 [1- i]的和.

(3)区间修改，区间查询

这类问题我上网搜了一些文章，感觉偏离了树状数组的本意，故在这里不做过多探究.自己就打算用线段树写这类问题了，大家如果感兴趣可以搜一搜这一类的文章读一读.

(4)扩展：

如果有这样的操作，i , k，将a[i]与k异或，即单点修改变成了异或修改，区间询问也变成了区间异或的结果，那该怎么办？
稍微改一下函数即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void update(int idx, int val)
{
    while(idx <= n)
    {
        c[idx] ^= val;
        idx += idx & -idx;
    }
}
int getsum(int idx)
{
    int sum = 0;
    while(idx > 0)
    {
        sum ^= c[idx];
        idx -= idx & -idx;
    }
    return sum;
}

题目链接:
http://acm.neu.edu.cn/hustoj/problem.php?id=1454
http://acm.dlut.edu.cn/problem.php?id=1263

区间修改的一些题目：
POJ 2352 Stars 排序，降维统计个数
POJ 3067 Japan 排序之后，就是统计逆序对数了
POJ 2481 Cows 这一题比较难，排序之后就和上面一样了
POJ 3321 Apple Tree 求结点的子树权值和.难点之处在于如何将数转换为连续区间,这就是dfs的巧妙之处
DOJ 1067 区间求和，单点修改.顺带求一个第K小数.开两个树状数组，一个求和，一个统计个数，注意一点的是对数组的数做个离散化处理
HOJ 1867 经理的烦恼 这题wa的我快吐了.可以先打素数表.首先判素数，居然不会超时.更新的时候注意更新前是否是素数
TJU 3243 Blocked Road 这题主要在于如果判断是否连通，直接开了2*n的数组，把环拆了

02 求序列第K小数

求序列的第K大数，可以转换为求序列的第N-K小数。

(1)方法一：二分搜索 复杂度：O(logN * logN)

树状数组统计比num小的数出现的次数，那么只要找到Getsum(i) == K，那么 i 就是第K小数。注意 ：getsum(i) for i in [1 - n]是一个递增序列，可以二分搜索

1
2
3
4
5
6
7
8
9
10
11
int find_Kth(int k)
{
    int l = 1, r = n, mid;
    while(l <= r)
    {
        mid = (l + r) >> 1;
        if(getsum(mid) >= k)r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

思考：一开始我认为如果序列中有重复的数怎么办?如果数列不是连续的，比如getsum(i) = k,但是i并没有出现在序列中，搜索到它就返回了怎么办？

注意这一句代码 if(getsum(mid) >= k)，我们每次二分的时候都尽量的往左边寻找第一个比k小的数，这样最后返回的 l 就一定在序列中存在，并且如果有重复的话，也一定是重复数字的第一个.

(2)方法二：二进制试加法 复杂度：O(logN)

1
2
3
4
5
6
7
8
9
10
11
int find_kth(int k)
{
    int cnt = 0, ans = 0;
    for(int i = 20; i >=0; i--)
    {
        ans += 1 << i;
        if(ans >= maxn-5 || cnt + c[ans] >= k)ans -= 1 << i;
        else cnt += c[ans];
    }
    return ans + 1;
}

算法流程：我们从二进制的最高位开始试加(默认最大值 <= 1 << 20，大概1000000)，统计ans之前数出现的次数，如果大于等于k，说明此次试加失败，该二进制位不可能是1，只能是0.那么我们最后的ans恰好比第K小数小1.原因(同方法一)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2852

03 逆序对数

树状数组还可以解决逆序对数的问题.每次插入到树状数组中的时候，询问插入在它之前的数中有几个比他大，这就是该数的逆序对数，累加到答案中.

题目练习:
POJ 2299 求逆序对数
HOJ 2275 Number Sequence 以a[i]为中心，分别统计左边比他小的数的个数，统计右边比他大的数的个数，开两个树状数组维护即可
Tyvj 1432 楼兰图腾 此题和上题差不多，oj的评测好像有点问题
POJ 1990 这一题比较难，巧妙之处在于求和的转换，排序之后就和上面一样了.
UVA 11610 Reverse Prime 综合题，筛完1e6之内的素数，reverse之后就是所有的7位的所求数.这些数末尾都至少有一个0，这样都除以10，减小数据规模。然后对每个数求其素因子数（不要忘了刚才除以10，还有2，5这两个素因子），然后离散化，开两个树状数组维护

扩展：

(1) 现在考虑这样一个问题：在序列 a[]中，交换a[i] 与 a[j] (i < j)，则序列的逆序对数奇偶性有何变化？

假设a[i]，a[i+1]，a[i+2]，····，a[j-1]，a[j].并假设a[i]和a[j]之间有m个数.

先考虑交换相邻的两个数.首先要确定的是，不会改变a[i]之前的数的逆序对数，也不会改变a[i+1]之后的数的逆序对数.如果a[i] > a[i+1]，交换后整个序列的逆序对数减1，反之则加1.也就是说，每一次相邻交换都会改变逆序对数的奇偶性.（相邻两个数相等的情况不考虑）

现在考虑交换a[i]，a[j].可以看做三个过程的相加.

  • 1) a[i]先和他后面的数一一做相邻交换，做了m次交换.

  • 2) a[i]与a[j]再做相邻交换，此时做了1次相邻交换.

  • 3) a[j]与他前面的数一一做相邻交换，交换到a[i]之前的位置，会有m次交换.

对换a[ i ]，a[ j ]总共做了2m + 1次相邻交换，由第一种考虑情况知，每做一次相邻交换都会改变奇偶性，所以此次对换i，j的操作也改变逆序对数的奇偶性.

题目链接: http://acm.dlut.edu.cn/problem.php?id=1284

(2)接着考虑一下，在序列 a[]中，交换a[i] 与 a[j] (i<j)，则序列的逆序对数个数有何变化？

自然而然的想到，如果要知道逆序对数的变化，我们需要知道在区间 [ i , j ]内，比a[ i ]小的数的个数 num_less_i，比 a [ i ]大的数的个数 num_larger_i，比a[ j ]小的个数num_less_j，比a[ j ]大的数的个数 num_larger_j.则个数变化可表示为：

1
change_num = - num_less_i + num_larger_i + num_less_j - num_larger_j

下面的问题是如何快速求出这些值.因为区间内的数的个数是一定的，为 j - i 个，所以只需要求 num_less_i，num_less_j 即可.

下面介绍一种O(1)的方法，但是空间开销比较大.（一直在寻找一种更好的方法，如果大家知道，欢迎与我讨论）

令cnt[i][j]表示到位置i为止(包括i)，比j小的数的个数.那么

1
2
3
4
5
6
num_less_i = cnt[j][a[i]] - cnt[i][a[i]];
num_larger_i = j - i - num_less_i;
num_less_j = cnt[j][a[j]] - cnt[i][a[j]];
num_larger_j = j - i  - 1 - num_less_j;
//第四行的减一是减去a[j]本身也算一个数
//大家自己可以画一画，不难推出

至于cnt数组完全可以预处理出来：

1
2
3
4
5
6
7
8
9
//递推求cnt数组
for(int i = 1; i <= n; i++)
{
   for(int j = 1; j <=n; j++)
   {
       if(a[i] < j)cnt[i][j] = cnt[i-1][j] + 1;
       else cnt[i][j] = cnt[i-1][j];
   }
}

此时就可以快速的查询交换a[ i ]，a[ j ]之后逆序对数的变化了.

题目链接: http://codeforces.com/contest/362/problem/C

(3)现在已知这样一个序列b，b[i] ( 1 <=i <= n )表示 i 在另外一个序列中的逆序对数，试问能否构造出这样的一个1-n的排列，满足b序列？

这个问题刚好和求逆序对数反了过来。举个例子，b序列 1 ,2 , 0, 1, 0.如何构造呢？

不妨试一试.1的逆序对数是1，也就是说，1在新序列中他的前面只能有1个比他大的数，但是1已经是最小数了，所以1必定处在第2的位置.构造序列： 1 _ 2的逆序对数是2，依照前面的分析方法，2必定处在第4的位置，即 1 2 。换句话说，2要找到第3个空位.再换个角度，对于位置序列（1,2,3,4,5），数字1已经占据了第2的位置，所以将序列中的2删除->(1,3,4,5)，那么我们要寻找的2的插入位置不就是第3小的元素，也就是第b[ i ]小元素么.求第K小元素上面已经分析过了，树状数组可以搞定.

1
2
3
4
5
6
7
8
//算法伪代码
//ans为构造的序列
//c[]为位置序列
for i in b[i]:
    pos = find_kth_elemnt( k )
    ans[pos] = i;
    //在c[]数组中删除
    update(pos,-1);

题目连接: http://acm.dlut.edu.cn/problem.php?id=1210

(4)仍是上一题中的序列b，b[i]表示原序列中位置 i 处的逆序对数，问你能否构造出原序列？(原序列为1-n的一个排列)

注意此题和上一题的不同.但是可以采用和上一题的相同的思路去解决.比如b序列 0, 1, 2, 0, 1

因为一个序列的第一个数的逆序对数总是为0，所以从前往后的分析不太靠谱.那么我们试一试从后向前分析.最后一个数的逆序对数为1，说明他前面只能有一个数比他大，显然最后一个数只能是4.即序列变成 4. 倒数第二个数的逆序对数为0，则同样可确定该数只能是5.序列变成 _5 4. 倒数第三个数的逆序对数为2，可确定该数为1.有什么规律呢？用cnt表示还剩下的数，每次要填的数，是不是第cnt - b[ i ]小的数呢？倒数第一个数的逆序对数为1，要填的是第 5 - 1小的数，也就是4. 然后倒数第二个数的逆序对数为0，要填第 4 - 0小的数，在剩余的数里面就是5.以此类推.

1
2
3
4
5
6
//算法伪代码
//ans为构造的序列
// for i = n; i > 0; i--
   num = find_kth_element( i - b[i])
   ans[i] = num
   update(num,-1)

题目链接: http://www.spoj.com/problems/ORDERS/

04 二维树状数组

这里有一篇不错的文章，介绍了二维树状数组的一些想法，推荐给大家。给出我自己的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void update(int i,int j, int val)
{
    for(int x = i; x <=n; x += x & -x)
    {
        for(int y = j; y <=n ;y += y & -y)
        c[x][y] += val;
    }
}
int getsum(int i,int j)
{
    int sum = 0;
    for(int x = i; x; x -= x & -x)
    {
        for(int y = j;y; y -= y & -y)
        sum += c[x][y];
    }
    return sum;
}

题目链接:

http://poj.org/problem?id=1195

http://poj.org/problem?id=2155

另外，想要按照难度刷题的朋友们可戳这里和这里，基本上汇集了oj的题目