成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

樹狀數(shù)組理解

Big_fat_cat / 1060人閱讀

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

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

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

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

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

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

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

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

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

如果這方法無法理解，建議看下二進制補碼

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

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

    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]
其中最后一個數(shù)是24，繼續(xù)分析 i = 24 binary i = 00011000 lowbit = 8 i-2^k = 16
s[24]=a[23]+a[22]+....+a[16]
最后一個數(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]，代碼實現(xiàn)如下

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

        return sum;
    }

上面只是我的個人理解，如有錯誤，敬請指正。

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68550.html

相關(guān)文章

  • 運用樹狀數(shù)組解決動態(tài)數(shù)組求和

    摘要：對于一組一維數(shù)組解決前項和，如果使用的方法需要的時間來找到前項數(shù)字的和，但是可以用的時間來更新對應(yīng)數(shù)字的值但是仍然需要的時間來更新牽扯到相應(yīng)數(shù)字?jǐn)?shù)組的和，相反可以使用樹狀數(shù)組來降低運行時間求數(shù)組內(nèi)一段數(shù)組的和，但同樣我們增加了更新樹狀數(shù)組內(nèi) 對于一組一維數(shù)組解決前n項和，如果使用linear scan的方法, 需要O(n)的時間來找到前n項數(shù)字的和，但是可以用O(1)的時間來更新對應(yīng)數(shù)...

    Barrior 評論0 收藏0

  • 用100行代碼畫出DOM樹狀結(jié)構(gòu)

    摘要：用行代碼畫出樹狀結(jié)構(gòu)這兩天寫了這樣一個小玩具，是一個可以把的樹狀結(jié)構(gòu)解析，并且畫出來的東西，把代碼寫到左邊，右邊就會自動生成啦。繪圖部分依賴了百度開源的，核心功能的實現(xiàn)只有行代碼。如果是或者標(biāo)簽，那么進入相應(yīng)的狀態(tài) 用100行代碼畫出DOM樹狀結(jié)構(gòu) 這兩天寫了這樣一個小玩具，是一個可以把DOM的樹狀結(jié)構(gòu)解析，并且畫出來的東西，把HTML代碼寫到左邊，右邊就會自動生成啦。 點這里看DEM...

    Galence 評論0 收藏0

  • localStorage實現(xiàn)本地儲存樹形菜單

    摘要：因為任務(wù)需要添加到樹的結(jié)構(gòu)上，所以要記錄任務(wù)是添加到哪個結(jié)點上的，需要為每個樹結(jié)點添加一個作為標(biāo)識以便于在結(jié)點上添加任務(wù)，樹狀結(jié)構(gòu)中每個結(jié)點的按照樹的先序遍歷將結(jié)點的依次儲存于數(shù)組中。 localStorage實現(xiàn)本地儲存樹形菜單 最近在寫一個Todo-list的頁面，頁面布局和操作都寫完后，想要用localStorage實現(xiàn)本地儲存。然而對儲存數(shù)據(jù)的方法一無所知，就先去了解了web的...

    William_Sang 評論0 收藏0

  • 關(guān)于樹形插件展示中數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換的算法

    摘要：舉例說明如下二維數(shù)據(jù)結(jié)構(gòu)總部二級門店三級門店二級門店樹狀數(shù)據(jù)結(jié)構(gòu)總部二級門店三級門店二級門店但在某些插件中，或在某些特殊場景中，我們有兩種數(shù)據(jù)結(jié)構(gòu)之間相互轉(zhuǎn)換的需求，需要自己寫一個輔助函數(shù)來完成。 問題背景 在一些目錄結(jié)構(gòu)、機構(gòu)層級等展示的場景中，我們經(jīng)常會用到一些成熟的樹形插件來進行輕松展示，比如ztree等。大多數(shù)插件會支持對兩種數(shù)據(jù)源格式的解析，一種是通用的二維數(shù)據(jù)結(jié)構(gòu)，一種是樹...

    王晗 評論0 收藏0

發(fā)表評論

0條評論

Big_fat_cat

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<