POJ2352 树状数组

POJ2352

假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。 来观察这个图： 令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现： C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 = A5 C6 = A5 + A6 C7 = A7 C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 ... C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16 这里有一个有趣的性质： 设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax， 所以很明显：Cn = A(n – 2^k + 1) + ... + An 算这个2^k有一个快捷的办法，定义一个函数如下即可： 1 2 3 int lowbit(int x){ return x&(x^(x–1)); } 利用机器补码特性，也可以写成： 1 2 3 int lowbit(int x){ return x&-x; } 当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可： step1:　令sum = 0，转第二步； step2:　假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步； step3: 令n = n – lowbit(n)，转第二步。 可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明： n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。 那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。 所以修改算法如下（给某个结点i加上x）： step1: 当i > n时，算法结束，否则转第二步； step2: Ci = Ci + x， i = i + lowbit(i)转第一步。 i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。 对于数组求和来说树状数组简直太快了! 注： 求lowbit(x)的建议公式： lowbit(x):=x and -x; 或lowbit(x):=x and (x xor (x - 1)); lowbit(x)即为2^k的值。

==================================================================================

http://www.cnblogs.com/hsd-/p/6139376.html

==================================================================================

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

#define N 32005
int c[N] = {0};
int a[N] = {0};
int lowbit(int x)
{
    return (x)&(-x);
}

void update(int pos, int add)
{
    while(pos < N)
    {
        c[pos] += add;
        pos += lowbit(pos);
    }
}

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

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int x,y;
        memset(a, 0, sizeof(a));
        memset(c, 0, sizeof(c));
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            update(x+1,1);
            a[getsum(x+1)]++;
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",a[i]);
        }
    }
}
           

              posted @ 2017-10-31 10:04 swallowblank 阅读(...) 评论(...) 编辑 收藏