# Segment Tree for RSM
class RSQ:
    N   # 完全二分木のノード数
    n   # 列の要素数 = 葉の数
    sum # 和を保持する配列

    # 最低限必要な列の要素数で初期化
    init(len):
        n ← 1
        while n < len:
            n ← n*2  # 葉の数nを2のべき乗にする
        N ← 2*n - 1  # 完全二分木のノード数を調整する 
        for i ← 0 to N-1:
            sum[i] ← 0

    # 区間[a, b)の和を求める		  
    findSum(a, b):
        return query(a, b, 0, 0, n)

    query(a, b, k, l, r):
        if r ≤ a or b ≤ l:
            res ← 0
        else if a ≤ l and r ≤ b:
            res ← sum[k]
        else:
            vl ← query(a, b, left(k), l, (l+r)/2)
            vr ← query(a, b, right(k), (l+r)/2, r)
            res ← vl + vr

        return res

    # k番目の要素にxを加算する
    update(k, x):
        k ← k + n - 1
        sum[k] ← sum[k] + x

        while  k > 0:
            k ← parent(k)
            sum[k] ← sum[left(k)] + sum[right(k)]

    left(k):
        return 2*k + 1

    right(k):
        return 2*k + 2

    parent(k):
        return (k - 1)/2