線段樹的數(shù)組大小下限及證明

手動博客搬家: 本文發(fā)表于20170820 20:23:52, 原地址https://blog.csdn.net/suncongbo/article/details/77432667

線段樹是一種將一個區(qū)間分成若干個子區(qū)間的數(shù)據(jù)結(jié)構(gòu)。它是一棵二叉樹，且滿足點i的子節(jié)點編號分別為2i和2i+1 (葉子節(jié)點除外).
因此，在已知區(qū)間[1, n]的情況下，我們需要知道其最大的節(jié)點編號。
首先由線段樹的性質(zhì)可以證明線段樹的深度不會超過\(ceil(\log_2 n)\)即\(floor(\log_2 n)+1\),由此可以得到節(jié)點的最大編號不會超過\[\sum_{i=0}^n 2^{floor(\log_2 n)+1}=2^{floor(\log_2 n)+2}-1=2^{floor(\log_2 n)}\times4-1\le2^{\log_2 n}\times4-1=4n-1\]
即：線段樹的數(shù)組下限為4*n-1.

發(fā)表于 2018-12-26 22:38 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部

總結(jié)

以上是生活随笔為你收集整理的线段树的数组大小下限及证明的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。