RominYue’s Blog

A lifeway of coders

树状数组小结

| Comments

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

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]z之后的数的逆序对数.如果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的题目

Comments