内容纲要

版权声明:“树状数组简介”中所用插图出自这里。链接到的是转载博文,转载作者未链接原文。侵删。其余讲解部分为本人原创。

1.例题(HDU1166

file
题意:给出一个序列,有如下操作:为其某子区间中的所有数价钱相同值,查询其某子区间内所有值的和。要求在查询操作后输出所求的和。

2.分析引入

乍看之下,这道题直接用for循环在指定区间内逐个求和。然而,必须注意这道题数据量给的非常大,直接使用for循环必定超时。那么,有没有一种方法,能降低序列求和的复杂度呢?或者更具体来说,正常的求和是逐个相加,对长为n需要进行n次加和操作,时间复杂度O(n)那么,有没有方法能使这种操作次数降低到n以下,时间复杂度达到O(logn)级别?这时,就需要引入树状数组这一数据结构了。

3.树状数组简介

对于一个常规数组a[]存储一个序列,a[i]表示的是序列中位置为i的元素的值。而对于一个树状数组c[]存储一个序列,c[i]表示的是序列中某一个以i为右界的子区间存储的值。那么这个区间具体会包含那些元素呢?
先回到树状数组本身,为什么会被称作树状数组?因为树状数组是基于二叉树的,如图是一个二叉树,令其叶子节点代表常规数组a[]中的a[1]a[8]
file
然后对二叉树做出以下变形:
file
可以发现,这个二叉树可以分为8列,这时,我们使用一个数组c[]表示每一列的最高点,并且使该二叉树根节点的值为其左右孩子节点的值之和。如图所示:
file
这里的c[]就是我们所说的树状数组。比如c[1] = a[1]c[4] = c[2] + c[3] + a[4] = a[1] + a[2] + a[3] a[4],换一种写法,a[1] + a[2] + ... + a[7] = c[4] + c[6] + c[7]这里我们就可以发现,原先的7个数加和,变为了现在的3个数加和,复杂度得到了有效的降低。
那么该如何判断所求区间中元素综合具体是树状数组中哪几位的和?可以通过二进制来寻找规律:
1 = (001) c[1] = a[1]
2 = (010) c[2] = a[2] + a[1]
3 = (011) c[3] = a[3]
4 = (100) c[4] = a[4] + a[3] + a[2] + a[1]
6 = (110) c[6] = a[6] + a[5]
7 = (111) c[7] = a[7]
可以发现,c[i] = c[i] + c[i - 1] + ... + c[i - n + 1]其中,n为i在二进制中最低位1在十进制中的值。比如(010),最低位1在第二位,在十进制中为2,(100)最低位1在第三位,在十进制中为4,那么如何求解n呢?这里引入lowbit。(见下一板块)

3.树状数组的基本操作

  • lowbit
    如何求解n?(n的意义见上文)求解n,需要“消除”所有比最高为1高的数,而且,在“消除”的同时,得要保证最高位1以及其后面的0不受影响,如何实现?
    这里想到使用补码。i的补码就是i的反码加一,比如22 = (10110),它的反码是(01001),它的补码是(01010),这时,将13的补码与13进行按位与,得到(00010) = 4,由此可见,比最低位1高位的数被“消除”,而最低为1以及其后的0被保护了,得到的4就是n。求和为c[i]的元素个数为lowbit(i)。以上,就是lowbit过程。根据一个数的负数在二进制中式这个数的补码的性质,可利用以下方法进行lowbit操作:
int lowbit(int x)
{
    return x & (-x);
}
  • 对某一区间内所有数求和
    树状数组的优点就体现在其低复杂度的求和操作。一个区间的和,可以视为从位置1开始到所求区间左界前一位与右界的两区间之差。即:
    a[l] + a[l + 1] + ... + a[r] = a[0] + a[1] + ... + a[r] - (a[0] + a[1] + ... + a[l - 1])
    然后要解决的,是对两区间的求和操作。为了描述方便,下面采用sum(x)表示a[1] + a[2] + ... + a[x]
    假设现在要求解sum(7),根据上文,sum(7) = c[7] + sum(6),这时需要求解sum(6),而sum(6) = c[6] + sum(4)sum(4) = c[4],于是sum(7) = c[7] + c[6] + c[4],而上文说到,求和为c[i]的元素个数为lowbit(i),于是,求和就很好实现了。
int query(int pos)
{
    int sum = 0;
    for(int i = pos;i > 0;i -= lowbit(i))
        sum += c[i];
    return sum;
}

int sum(int l, int r)
{
    return query(r) - query(l);
}
  • 改变一个元素的值
    按照树状数组的性质,改变第i个元素的值,改变的显然是c[i]以及其后的值,因为c[i]存储的是第i - lowbit(i) + 1到第i位的值。还是由于求和为c[i]的元素个数为lowbit(i),可以按以下方法实现:(很多教程说这是求和的逆过程,本人不完全赞同,因为起点是不一样的,但是所用的原理是相同的)
void update(int pos,int x)
{
    for(int i = pos;i <= n;i += lowbit(i)) //n为序列所含元素个数
        c[i] += x;
}

4.例题(HDU1166)AC代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define M 1000000007
using namespace std;
typedef long long LL;
const int maxn = 5e4+5;

int c[maxn];
int n,T,tmp;
char s[20];

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

void update(int pos,int x)
{
    for(int i = pos;i <= n;i += lowbit(i))
        c[i] += x;
}

int query(int pos)
{
    int sum = 0;
    for(int i = pos;i > 0;i -= lowbit(i))
        sum += c[i];
    return sum;
}

// int sum(int l, int r)
// {
//     return query(r) - query(l);
// }

int main()
{
    scanf("%d", &T);
    for(int t = 1;t <= T;++t)
    {
        scanf("%d", &n);
        memset(c,0,sizeof(c));
        for(int i = 1;i <= n;++i)
        {
            scanf("%d", &tmp);
            update(i,tmp);
        }
        printf("Case %d:\n", t);
        while(true)
        {
            scanf("%s", s);
            if(s[0] == 'Q')
            {
                int l,r;
                scanf("%d%d", &l, &r);
                printf("%d\n", query(r) - query(l - 1));
            }
            if(s[0] == 'A')
            {
                int pos,x;
                scanf("%d%d", &pos, &x);
                update(pos,x);
            }
            if(s[0] == 'S')
            {
                int pos,x;
                scanf("%d%d", &pos, &x);
                update(pos,-x);
            }
            if(s[0] == 'E')
                break;
        }
    }

    return 0;
}

file

ACM暑假学习与复习笔记:传送门

发表评论

电子邮件地址不会被公开。 必填项已用*标注