(問題 10)Segment Treeの総まとめ VB(Beta)編（paizaランク S 相当）

(はじめに)

問題 9 まででSegment Treeを一通り作成することが出来ました。

class SegTree():
    def calc(self,a, b): #行いたい処理
        return max(a, b)

    def e(self): #単位元
        return 0

    def __init__(self, n, A):
        #完全2分木を作る
        #N = 2 ** k ≧ n となるようにする。(葉の数がnより多くなるようにする。)
        self.k = (n - 1).bit_length() #bit_lengthメソッドにより取得が出来る。
        N = 2 ** (self.k)
        self.N = N
        self.Tree = [self.e()] * (2 * N - 1)
        #葉の部分に初期要素を入れる
        for i in range(n):
            self.Tree[N - 1 + i] = A[i]
        #葉から近い順にそれぞれの葉以外の頂点の計算を行う
        for i in range(N - 2, -1, -1):
            self.Tree[i] = self.calc(self.Tree[2 * i + 1], self.Tree[2 * i + 2]) #頂点iの子は2i+1,2i+2、そこの2つを用いて計算を行う

    def renewal(self, ind, x): #A[ind]をxに更新
        T = self.N - 1 + ind #A[ind]に対応する場所
        self.Tree[T] = x
        while T > 0: #根にたどるまで更新を続ける
            T = (T - 1) // 2
            self.Tree[T] = self.calc(self.Tree[2 * T + 1], self.Tree[2 * T + 2])

    def product(self, L, R): #A[L]からA[R]までの計算結果を返す
        ans = self.e() #答え、単位元で初期化
        p = L
        while p <= R: #出来るだけ貪欲にlからrまで進める
            m = p
            cnt = 0 #何回 2 で割れるか計算する。
            #ここの演算を適当なものに変えることで計算量が少し改善する
            while m % 2 == 0:
                if m == 0: #0のときだけ無限に割れてしまうため例外処理をする。
                    cnt = 10 ** 9
                    break
                cnt += 1
                m = m // 2
            cnt2 = (R - p + 1).bit_length() - 1
            l = min(cnt, cnt2) #SegTreeの性質上、lから始まるものの最大幅は2 ** cntである。範囲を飛び出してしまうため2 ** cnt2 より大きくは進めない。
            #pからp+2**l-1までの計算結果が入っている配列の場所を探す
            kdash = self.k - l
            ans = self.calc(ans, self.Tree[(2 ** kdash - 1) + p // 2 ** l]) #(2 ** kdash  - 1) で幅 2 ** l の一番左の配列のindexをとり、そこからp // 2 ** l の分だけずれる
            p += 2 ** l
        return ans

では、最後にここまでの総まとめをしましょう。

(問題)

長さが n の配列 A が与えられます。Q 個のクエリが与えられるので順番に処理を行ってください。i 番目のクエリは以下のどちらかです。

q_i = 1 のとき A_{a_i},A_{a_i + 1},...,A_{b_i} の中で最も大きい整数を出力する。

q_i = 2 のとき A_{a_i} を b_i に変更する。