概要

売上配列に対して「区間和の取得」と「一点更新」を \(Q\) 回処理する問題です。各操作を高速に行うために Fenwick Tree（Binary Indexed Tree）を使います。

考察

この問題では次の 2 種類のクエリを繰り返し処理します。

• タイプ1: \([L, R]\) の売上合計（区間和）
• タイプ2: 店舗 \(X\) の売上を \(V\) に変更（一点更新）

素朴に、タイプ1のたびに \(S_L + S_{L+1} + \cdots + S_R\) をそのまま足すと、1回のクエリに最大 \(O(N)\) かかります。最悪の場合 \(Q=2\times10^5\) なので、合計で \(O(NQ)\) となり現実的な時間では間に合いません（TLE）。

一方、累積和（prefix sum）を事前に作れば区間和は \(O(1)\) で出せますが、タイプ2で値を更新するたびに累積和を作り直すと \(O(N)\) かかり、やはり間に合いません。

そこで「一点更新」と「累積和（prefix sum）の取得」をどちらも \(O(\log N)\) で行えるデータ構造が必要になります。これを満たす代表が Fenwick Tree です。

アルゴリズム

Fenwick Tree（Binary Indexed Tree）は、次を高速に行えるデータ構造です。

• add(i, x): 配列の \(i\) 番目に \(x\) を加算（差分加算）
• sum(i): \(S_1 + S_2 + \cdots + S_i\)（1〜i の累積和）を取得

区間和は累積和を使って \(\sum_{k=L}^{R} S_k = \mathrm{sum}(R) - \mathrm{sum}(L-1)\) で求められます。

また、今回の更新は「\(S_X\) を \(V\) に変更」なので、Fenwick Tree には差分だけを加えます。現在値を \(A[X]\) として保持しておけば、 \(\Delta = V - A[X]\)を計算して add(X, Δ) を行えばよいです。その後 \(A[X] = V\) に更新します。

具体例

\(S = [3, 1, 4, 1, 5]\) のとき、\([2,4]\) の和は

• \(\mathrm{sum}(4)=3+1+4+1=9\)
• \(\mathrm{sum}(1)=3\)
• よって \(9-3=6\)

店舗3を \(4 \rightarrow 10\) に更新するときは差分 \(\Delta = 10-4=6\) を add(3, 6) して整合性を保ちます。

計算量

• 時間計算量: 初期構築 \(O(N\log N)\)、各クエリ \(O(\log N)\) なので全体で \(O((N+Q)\log N)\)
• 空間計算量: Fenwick Tree と現在値配列で \(O(N)\)

実装のポイント

• Fenwick Tree は 1-indexed（添字が \(1\) から）で実装すると簡潔です（コードでも配列サイズを \(N+1\) にしています）。
• 「値を \(V\) に更新」はそのまま代入ではなく、差分 \(\Delta=V-A[X]\) を計算して add するのが重要です。
• 入力が大きいので、sys.stdin.buffer.read() でまとめて読み込み、出力も配列に溜めて最後にまとめて出すと高速です。

ソースコード

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    A = [0] * (N + 1)
    fw = Fenwick(N)
    for i in range(1, N + 1):
        v = next(it)
        A[i] = v
        fw.add(i, v)

    out = []
    for _ in range(Q):
        t = next(it)
        if t == 1:
            L = next(it)
            R = next(it)
            out.append(str(fw.sum(R) - fw.sum(L - 1)))
        else:
            X = next(it)
            V = next(it)
            delta = V - A[X]
            if delta:
                fw.add(X, delta)
                A[X] = V

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。