首页 > 代码库 > Binary Indexted Tree 树状数组入门

Binary Indexted Tree 树状数组入门

感谢http://www.cnblogs.com/xudong-bupt/p/3484080.html

树状数组(BIT)是能够完成下述操作的数据结构

  给定一初始值全为零的数列a1,a2a,a3...,an

  1.给定i,计算a1+a2+...+ai

  2.给定i和x,执行ai+=x

 

BIT的结构:

技术分享

数组bit[N]

  bit[1]=C1=A1;bit[2]=C2=C1+A2;

  BIT就是使用数组来维护上面所说的部分和

  以1结尾的1,3,5,7长度为1

  以1个0结尾的2,6长度为2

  以两个0结尾的4长度为4

这样,编号的二进制就能和区间对应起来

通过这个性质,实现上述功能

 

修改操作 :

修改a[k]后,c数组的哪些元素受到影响? 

p1=k肯定受到影响, 设pi的父亲为p(i+1),则

p(i+1)=pi+2^L,L为pi二进制中末尾0的个数

给a[3]增加x,则p1=3, p2=3+20=4, p3=4+22=8, p4=8+23=16>9,因此修改c[3],c[4],c[8]

它所有的后继(祖先)受影响

找后继

求和操作 :

设要求前k项的和,则从最后一项开始 k1=k

 k(i+1)=ki-2^s,

s为ki二进制末尾0的个数  k=7,

则k1=7, k2=k1-20=6, k3=k2-21=4, k4=k3- 22=0,

因此前7项和为c[7]+c[6]+c[4]

 

  1) a[]: 保存原始数据的数组。(操作(1)求其中连续多个数的和,操作(2)任意修改其中一个元素)

    e[]: 树状数组,其中的任意一个元素e[i]可能是一个或者多个a数组中元素的和。如e[2]=a[1]+a[2]; e[3]=a[3]; e[4]=a[1]+a[2]+a[3]+a[4]。 

  2) e[i]是几个a数组中的元素的和?

    如果数字 i 的二进制表示中末尾有k个连续的0,则e[i]是a数组中2^k个元素的和,则e[i]=a[i-2^k+1]+a[i-2^k+2]+...+a[i-1]+a[i]

    如:4=100(2)  e[4]=a[1]+a[2]+a[3]+a[4];

      6=110(2)  e[6]=a[5]+a[6]

      7=111(2)  e[7]=a[7]

  3) 后继:可以理解为节点的父亲节点。离它最近的,且编号末位连续0比它多的就是的父亲,如e[2]是e[1]的后继;e[4]是e[2]的后继。

      如e[4] = e[2]+e[3]+a[4] = a[1]+a[2]+a[3]+a[4] ,e[2]、e[3]的后继就是e[4]。

      后继主要是用来计算e数组,将当前已经计算出的e[i]添加到他们后继中。

    前驱:节点前驱的编号即为比自己小的,最近的,最末连续0比自己多的节点。如e[7]的前驱是e[6],e[6]的前驱是e[4]。

        前驱主要是在计算连续和时,避免重复添加元素

      如:Sum(7)=a[1]+...+a[7]=e[7]+e[6]+e[4]。(e[7]的前驱是e[6], e[6]的前驱是e[4])

    计算前驱与后继:

      lowbit(i) = ( (i-1) ^ i) & i ;

      节点e[i]的前驱为 e[ i - lowbit(i) ];

      节点e[i]的后继为 e[ i + lowbit(i) ]

核心思想:

    (1)树状数组中的每个元素是原数组中一个或者多个连续元素的和

    (2)在进行连续求和操作a[1]+...+a[n]时,只需要将树状数组中某几个元素的和即可。时间复杂度为O(lgn)

    (3)在进行修改某个元素a[i]时,只需要修改树状数组中某几个元素的和即可。时间复杂度为O(lgn)

 

一维树状数组常用的3个函数

int lowbit(int x) //取x的最低位1,比如4,则返回4,如5,则返回1
{
    return x&(-x);
}

void update(int i, int val)  //将第i个元素增加val
{
    //i的祖先都要增加val
    while(i <= n)
    {
        sum[i] += val;
        i += lowbit(i);   //将i的二进制未位补位得到其祖先
    }
}

int Sum(int i)   //求前i项的和
{
    int s = 0;
    //将前i项分段
    while(i > 0)
    {
        s += sum[i];
        i -= lowbit(i);  //去掉i的二进制最后一个
    }
    return s;
}

基本功能

技术分享
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char order[10];
int a[50010];
inline int lowbit(int k)
{
    return k&-k;
}

inline void update(int i,int N,int plus)///界限N,为第i项加上plus,对应包含它的项也要改变
{
    while(i<=N)
    {
        a[i]+=plus;
        i+=lowbit(i);///后继改变
    }
}
inline int getsum(int k)///求第1到第k项的和
{
    int sum=0;
    while(k)
    {
        sum+=a[k];
        k-=lowbit(k);
    }
    return sum;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        int x;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            update(i,n,x);
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("求前5项和:\n");
        printf("%d\n",getsum(5));
        printf("求3-6项和:\n");
        printf("%d\n",getsum(6)-getsum(3)+a[3]);
    }
    return 0;
}
View Code

 

 

以下数组下标均默认从1开始

应用一

假如给你一个数组a[ ] = {2,5,3,4,1},求b[i],b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左边)小于等于a[i]的数的个数。对此例b[] = {0,1,1,2,0}。 那么该如何去求得b[i]呢?

解法:假如要得到b[4]的值,对于a[4] = 4. 我们 只要得到在a[1],a[2],a[3] 中出现小于等于4的个数,即1,2,3,4的个数,此例即为2. a[1] = 2 < a[4], a[3] = 3 < a[4]. 所以b[4] = 2;其他的以此类推. 求b[i]的值,需要得到在a[1],a[2]....a[i-1]中出现小于等于a[i]的个数,即1,2...a[i]的个数. 相当于求前a[i]项的和,可用到树状数组. 

具体操作

for(int i=1; i<=n; i++)

{

b[i] = getSum(a[i]); //求前a[i]项的和

update(a[i],1);      //第a[i]个元素+1

}

应用二

假如给你一个数组a[ ] = {2,5,3,4,1},求b[i],b[i] 表示在a[1],a[2]...a[i-1]中(即位置i的左边)大于等于a[i]的数的个数。对此例b[] = {0,0,1,1,4}。 那么该如何去求得b[i]呢?

解法1: 只需要先将数组a倒过来编号,即将a转换为,a[] ={4,1,3,2,5}.此时具体的操作如应用一

解法2:改变更新路径和求和路径

 

Binary Indexted Tree 树状数组入门