樹(shù)狀數(shù)組理解

Big_fat_cat 發(fā)布于2019-08-15 14:20 / 1059人閱讀

摘要：無(wú)意間看到樹(shù)狀數(shù)組，查了很多資料被各種圖和公式繞暈了，下面記錄一點(diǎn)個(gè)人理解。

無(wú)意間看到樹(shù)狀數(shù)組，查了很多資料被各種圖和公式繞暈了，下面記錄一點(diǎn)個(gè)人理解。

假設(shè)數(shù)組a[0],a[1],a[2],.....,a[n]，記0-m元素之和為sum(m) (0=

遍歷累加0-m 時(shí)間復(fù)雜度O(m)，空間復(fù)雜度O(1)

增加輔助數(shù)組s[0],s[1],s[2],.....,s[n] 時(shí)間復(fù)雜度O(1)，空間復(fù)雜度O(n)

當(dāng)我們頻繁的求s(m)時(shí)，第一種方法不適用，當(dāng)我們頻繁的修改數(shù)組a時(shí)，第二種方法每次都要修改數(shù)組s，修改數(shù)組s的時(shí)間復(fù)雜度為O(n)

而樹(shù)狀數(shù)組可以很好解決這種場(chǎng)景，它類似方法二
方法二中我們定義s[m] = a[m]+a[m-1]+a[m-2]+....+a[0]
樹(shù)狀數(shù)組中我們定義s[m]= a[m-1]+a[m-2]+....+a[i-2^k],其中k為m的二進(jìn)制的第一個(gè)1前0的個(gè)數(shù)
ps:有些資料是m至i-2^k+1,那是數(shù)組下標(biāo)從1開(kāi)始計(jì)數(shù)的，這里下標(biāo)從0開(kāi)始，因此有所區(qū)別

舉個(gè)例子：10的二進(jìn)制1010，因此k=1；24的二進(jìn)制11000，因此k=3
我們記lowbit(m)=2^k,即有l(wèi)owbit(10)=2,lowbit(24)=8
可以發(fā)現(xiàn)2的二進(jìn)制是10,8的二進(jìn)制是1000，因此lowbit的實(shí)現(xiàn)很簡(jiǎn)單

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

如果這方法無(wú)法理解，建議看下二進(jìn)制補(bǔ)碼

接下來(lái)數(shù)組s就有的一個(gè)公式
s[m]=a[m-1]+a[s-2]+....+a[i-lowbit(m)]

我覺(jué)得樹(shù)狀數(shù)組講到這里就可以了，為了便于理解，我舉一個(gè)例子，測(cè)試代碼如下

    public static void main(String[] args) {
        for (int i = 0; i < 30; i++) {
            System.out.println("i = " + intFixedString(i) + " binary i = " + intBinaryString(i) + " lowbit = " + lowbit(i) + " i-2^k = " + (i - lowbit(i)));
        }
    }

    public static String intBinaryString(int i) {
        return Integer.toBinaryString((i & 0xFF) + 0x100).substring(1);
    }

    public static String intFixedString(int i) {
        return i < 10 ? i + " " : i + "";
    }

打印結(jié)果

假設(shè)求sum(28)，我們分析一下 i = 28 binary i = 00011100 lowbit = 4 i-2^k = 24
s[28]=a[27]+a[26]+....+a[24]
其中最后一個(gè)數(shù)是24，繼續(xù)分析 i = 24 binary i = 00011000 lowbit = 8 i-2^k = 16
s[24]=a[23]+a[22]+....+a[16]
最后一個(gè)數(shù)是16，繼續(xù)分析 i = 16 binary i = 00010000 lowbit = 16 i-2^k = 0
s[16]=a[15]+a[14]+....+a[0]

很容易發(fā)現(xiàn)sum(28)=a[28]+s[28]+s[24]+s[16]，代碼實(shí)現(xiàn)如下

    public int sum(int m) {
        int sum = a[m];
        while (m >= 0) {
            sum += s[m];
            m = m - lowbit(m);
        } 

        return sum;
    }

上面只是我的個(gè)人理解，如有錯(cuò)誤，敬請(qǐng)指正。

參考：http://www.cppblog.com/menjit...