\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年5月28日 星期四

[ Persistent Binary Index Tree ] 持久化BIT

(二分索引樹)BIT是一種容易實現的資料結構,但在持久化的應用上是非常困難的,但我們可以犧牲些許的複雜度來簡化其實現方式

一般區間和的BIT長這樣:

這是持久化的版本(也可以用pair來實作):
可以知道其更新的複雜度為\(\ord{logN}\),查詢複雜度為\(\ord{logN*logQ}\),Q是查詢次數

沒有留言:

張貼留言