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 閱讀(...) 評論(...) 編輯 收藏