树状数组

  树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。
  树状数组十分容易实现,代码量小,时间复杂度低,并且经过数学处理后也可以实现成段更新。线段树也可以做到和树状数组一样的效果,但是代码要复杂得多。不过要注意,一般情况下树状数组能解决的问题线段树都能解决,反之有些线段树能解决的问题树状数组却不行。

代码如下:


int lowbit(int x)
{
    return x & (-x);
}
void modify(int x,int add)//一维
{  
    while(x<=MAXN)  
    {      
        a[x]+=add;    
        x+=lowbit(x);
    }
}
int get_sum(int x)
{  
    int ret=0;
    while(x!=0)  
    {       
        ret+=a[x];   
        x-=lowbit(x);   
    }  
    return ret;
}
void modify(int x,int y,int data)//二维
{
    for(int i=x;i<MAXN;i+=lowbit(i))
        for(int j=y;j<MAXN;j+=lowbit(j))
            a[i][j]+=data;
}
int get_sum(int x,int y)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            res+=a[i][j];
    return res;
}

例题

  • poj 2299 Ultra-QuickSort
      题意为给定一个序列,求该序列中的逆序数的对数。
      树状数组求解的思路:开一个能大小为这些数的最大值的树状数组,并全部置0。从头到尾读入这些数,每读入一个数就更新树状数组,查看它前面比它小的已出现过的有多少个数sum,然后用当前位置减去该sum,就可以得到当前数导致的逆序对数了。把所有的加起来就是总的逆序对数。
      题目中的数都是独一无二的,这些数最大值不超过999999999,但n最大只是500000。如果采用上面的思想,必然会导致空间的巨大浪费,而且由于内存的限制,我们也不可能开辟这么大的数组。因此可以采用离散化的方式,把原始的数映射为1-n一共n个数,这样就只需要500000个int类型的空间。

代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 500005;

struct Node
{
    int val;
    int pos;
};

Node node[N];
int c[N], reflect[N], n;

bool cmp(const Node& a, const Node& b)
{
    return a.val < b.val;
}

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

void update(int x)
{
    while (x <= n)
    {
        c[x] += 1;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main()
{
    while (scanf("%d", &n) != EOF && n)
    {
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &node[i].val);
            node[i].pos = i;
        }
        sort(node + 1, node + n + 1, cmp);   //排序
        for (int i = 1; i <= n; ++i) reflect[node[i].pos] = i;   //离散化
        for (int i = 1; i <= n; ++i) c[i] = 0;   //初始化树状数组
        long long ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            update(reflect[i]);
            ans += i - getsum(reflect[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
  • poj 3468 A Simple Problem with Integers

      题意:给你一个数列,每次询问一个区间的和,或者每次将一个区间的所有元素都加上一个数.
      树状数组也可以实现区间更新,不过相比要比线段树区间更新难理解一些,具体过程如下:
      首先,看更新操作update(s,t,d)把区间A[s]...A[t]都增加d,我们引入一个数组delta[i],表示A[i]...A[n]的共同增量,n是数组的大小。那么update操作可以转化为:令delta[s] = delta[s]+d,表示将A[s]...A[n]同时增加d,但这样A[t+1]...A[n]就多加了d,所以再令delta[t+1] = delta[t+1]-d,表示将A[t+1]...A[n]同时减d。  
      然后来看查询操作query(s, t),求A[s]...A[t]的区间和,转化为求前缀和,设sum[i] = A[1]+...+A[i],则 A[s]+...+A[t] = sum[t] - sum[s-1], 那么前缀和sum[x]又如何求呢?它由两部分组成,一是数组的原始和,二是该区间内的累计增量和,把数组A的原始值保存在数组org中,并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i),那么sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1 = org[1]+...+org[x] + segma(delta[i]*(x+1-i)) = segma(org[i]) + (x+1)*segma(delta[i])-segma(delta[i]*i),1<=i<=x=segma(org[i]-delta[i]*i)+(x+1)*delta[i], i<=1<=x.
      这里就可以转化为两个个数组,这其实就是三个数组org[i],delta[i]和delta[i]*i的前缀和,org[i]的前缀和保持不变,事先就可以求出来,delta[i]和delta[i]*i的前缀和是不断变化的,可以用两个树状数组来维护。

    代码如下:

#include<cstdio>
#include<cstring>
using namespace std;

long long int n;
long long bit0[200000],bit1[200000];

long long sum(long long *b,int i)
{
    long long s=0;
    while(i>0)
    {
        s+=b[i];
        i-= i &(-i);
    }
    return s;
}

void add(long long *b,long long  int i,long long int v)
{
    while(i<=n)
    {
        b[i]+=v;
        i+=i&(-i);
    }
}


int main()
{
    long long int i,j,k,a,b,c,m;
    long long res;
    char ch[100];
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        memset(bit0,0,sizeof(bit0));
        memset(bit1,0,sizeof(bit1));
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a);
            add(bit0,i,a);
        }
        for(k=0;k<m;k++)
        {
            scanf("%s",ch);
            if(ch[0]=='C')
            {
                scanf("%lld%lld%lld",&a,&b,&c);
                add(bit0,a,-c*(a-1));
                add(bit1,a,c);
                add(bit0,b+1,b*c);
                add(bit1,b+1,-c);
            }
            else
            {
                res=0;
                scanf("%lld%lld",&a,&b);
                res+=sum(bit0,b)+sum(bit1,b)*b;
                res-=sum(bit0,a-1)+sum(bit1,a-1)*(a-1);
                printf("%lld\n",res);
            }
        }
    }
    return 0;
}

results matching ""

    No results matching ""