(はじめに)

問題 4,5 にてBITの一点加算を行ってきました。

最後にBITで区間総和を高速に処理する方法をやっていきます。

class BIT():

    def cnt2(self, I): #2で何回割れるか計算する
        k = 0
        while I % 2 == 0:
            k += 1
            I = I // 2
        return k

    def __init__(self, n, A): #BITの作成
        self.Tree = [0]* (n + 1) #0で初期化
        self.n = n
        for i in range(1, n + 1):
            k=self.cnt2(i)
            for j in range(i - 2 ** k, i): #インデックス注意
                self.Tree[i] += A[j]

    def add(self, id, x): #A[id]にxを足す作業
        self.Tree[id] += x
        now = id
        while True:
            k = self.cnt2(now)
            now = now + 2 ** k #親に移動
            if now > self.n: #該当するものがないなら根にたどり着いたということ
                break
            self.Tree[now] += x #加算処理

    def sum(self, id): #A[id] までの累積和を計算
        #問題 6,7 で実装

(BITの区間総和について)

区間総和について考えていきます。

前から m 項の和をBITの要素の和として計算することを考えます。

まず、j > m を満たす任意の j について、BIT_j には A_j が加算されているので、ここの部分を使うことはできません。

よって、BIT_j (j ≦ m) の要素のみを考えていきます。

A_m の要素は BIT_m にしか含まれていないので、BIT_m を使う必要があります。

また、BIT_m には、m を 2 で割ることが出来る回数の最大値を p としたとき、A_{m - 2 ^ p + 1} から A_m までの 2 ^ p 個の要素の総和が入っています。つまり、前から m 項の和は前から m - 2 ^ p 項の和と BIT_m の和で表すことが出来ます。

そして、前から m - 2 ^ p 項の和は、m を m - 2 ^ p と置きかえて同様に計算することになり、以後 m が 0 になるまで繰り返し計算することになります。

では、実際にインデックス計算を行いましょう。

(問題)

Q 個のクエリが与えられます。順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。

整数 t_i が与えられる。m_0 = t_i とし、m_{i + 1} = m_i - 2 ^ p_i (p_i は m_i を 2 で割ることが出来る回数の最大値)とし、ある整数 k においてはじめて m_k = 0 になったとする。配列 M = (m_0, m_1, ..., m_k) を出力する。