数据结构:树状数组

区间求和,单点更新

Posted by chochi on November 16, 2017

树状数组

  • 连续的数组空间,人为的使用二进制末尾零的个数限定下标,使其成为一颗树。
  • 使用于给定Len个元素A[1~N],以O(logN)的复杂度求[l,r]的累积和,或者更改A[i]的值。
  • 数组下标必须从 1 开始

树状数组的逻辑关系

BIT逻辑

  • 对于节点x,其父亲节点为记为F,记x在树中的高度为kk为节点x的二进制数中末尾零的个数。
F = x + lowbit(x) 
lowbit(x) = 2^k = (x)and (-x)  
     

举个栗子:

设 x=4 ,则 k=2,lowbit(x) = 4, F = x + lowbit(x) = 8 
而在程序中,是巧妙的运用了位运算 x&(-x), 位运算过程如下:
4 = (0100)
-4 = -(1100)
4 and (-4) = (0100) = 4
  • A数组为我们的原始数据数组,C[i]代表的是子树叶子权值节点之和。
  • 则上图的节点对应关系如下。
C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+......A[i];
  • Q: A数组[1,5]区间的所有值之和
    • c[4] = A[1]+A[2]+A[3]+A[4]
    • c[6] = A[5] + A[6]
    • ans = c[4] + c[6]
      • ans = c[6]
      • lowbit(6) = 2 , 6-2 =4
      • ans = ans + c[4]

树状数组实现代码

//更新操作,参数(当前更改的元素下表,更改的值)

void update(int index,int ival)
{
    while( index < len )
    {
        bit[index] += ival;
        index += lowbit( index) ;//所有的祖先都更新

    }
}
//连续和询问,参数(c数组,右区间)

int qurey(int bit[], int index)
{
    int ans = 0;
    while(index>0)
    {
        ans += bit[ index ];
        index -= lowbit( index );//累加所有子树
    }
    return ans;
}

例题讲解

POJ 2352 stars image

  在二维坐标轴上给定一些星星的坐标,如上图的下三角形所示,星星的数据已经按Y坐标轴升序排列好,如5号星星的左下方有3颗星星,则规定5号星星在第三层;同理可得,一层有两颗星星,分别是4号和2号,而0层有1号星星。输入N个星星,输出0 ~ N-1层每层有几个星星。

  思路:因为已经Y排序好,只要按输入的顺序,每次去计算当前编号的星星的区间和,如输入星星的坐标为(5,1),那么只要计算A[1]+..+A[5]的累积和,即是该颗星星所在层数。

#include<iostream>

#include<stdio.h>

#include<string.h>

#define CLEAR(num,val) memset(num,val,sizeof(num))

using namespace std;
const int maxn = 32000+5;
int c[maxn];
int cnt[15000+5];
using namespace std;
inline int lowbit( int x){
    return x & ( -x );
}
void add( int index,int val){
    while( index < maxn){
        c[index] += val;
        index += lowbit(index);
    }
}
int count_stars(int x){
    int sum = 0;
    while( x > 0 ){
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}
int main()
{
    int n,x,y;
    while( ~scanf("%d",&n)){
        CLEAR(c,0);
        CLEAR(cnt,0);
        for(int i=0;i<n;++i){
            scanf("%d%d",&x,&y);
            ++x;
            cnt[ count_stars(x) ]++;
            add(x,1);
        }
        for( int i = 0 ; i <n;++i)
            printf("%d\n",cnt[i]);
    }
    return 0;
}

δγθ