概要

この問題は、配列の特定の要素を更新する「点更新」と、指定された範囲の合計を求める「区間和取得」の2種類の操作を高速に行う問題です。

考察

まず、素朴な方法（シミュレーション）を考えてみましょう。

• 更新クエリ: 配列の値を書き換えるだけなので \(O(1)\) で終わります。
• 合計クエリ: 店舗 \(L\) から \(R\) までを足し合わせるため、最悪の場合 \(O(N)\) かかります。

クエリの回数が \(Q\) 回あるため、全体の計算量は \(O(NQ)\) となります。今回の制約では \(N, Q \leq 2 \times 10^5\) なので、最悪の場合 \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2秒程度）に間に合いません。

この「点更新」と「区間和取得」の両方を高速に行うためには、フェニック木（Fenwick Tree / Binary Indexed Tree）やセグメント木（Segment Tree）といったデータ構造を利用するのが一般的です。これらのデータ構造を使うと、どちらの操作も \(O(\log N)\) で処理できるようになります。

アルゴリズム

今回の解答では、実装がシンプルで定数倍の計算も速い フェニック木 (BIT) を使用しています。

フェニック木 (BIT) とは

累積和の考え方を応用したデータ構造です。各ノードが特定の区間の和を保持することで、以下の操作を可能にします。

1. 累積和の取得: \(1\) 番目から \(i\) 番目までの合計を \(O(\log N)\) で計算します。
   • これを利用して、区間 \([L, R]\) の和は (1からRまでの和) - (1からL-1までの和) として求められます。
2. 要素の更新: 特定の要素に値を加算する操作を \(O(\log N)\) で行います。
   • 今回の問題は「値を \(V\) に書き換える」操作なので、更新後の値 - 現在の値 を計算し、その差分を加算することで対応します。

工夫した初期化

BITを空の状態から \(N\) 回加算して構築すると \(O(N \log N)\) かかりますが、今回のコードでは \(O(N)\) で構築する手法を採り入れています。各要素の値を親ノードに順次伝播させることで、より高速に初期化を行っています。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 初期構築に \(O(N)\)、各クエリの処理に \(O(\log N)\) かかります。
  • \(N, Q = 2 \times 10^5\) のとき、計算回数はおよそ数百万回となり、Pythonでも十分に間に合います。
• 空間計算量: \(O(N)\)
  • 売上を管理する配列 S と、BIT本体の配列 bit で \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで大量の入力を扱う場合、input() を繰り返すと遅くなるため、sys.stdin.read().split() で一括取得し、イテレータで処理しています。また、出力も sys.stdout.write を使ってまとめて出力することで高速化しています。
• 1-indexed: フェニック木はビット演算を利用する性質上、配列のインデックスを \(1\) から始めると実装が非常にスッキリします。
• 差分更新: クエリ2では「値を \(V\) にする」必要があるため、現在の値 S[X] を保持しておき、V - S[X] という差分を BIT に加算するのがポイントです。

ソースコード

import sys

def solve():
    # データの読み込みを高速化するため、sys.stdin.read().split() を使用して
    # すべての入力を一括で取得し、イテレータに変換します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    N = int(next(it))
    Q = int(next(it))
    
    # 各店舗の現在の売上額を保持する配列 (1-indexed)
    S = [0] * (N + 1)
    # Fenwick Tree (Binary Indexed Tree) の配列 (1-indexed)
    bit = [0] * (N + 1)
    
    # Fenwick Tree を O(N) で初期化
    for i in range(1, N + 1):
        val = int(next(it))
        S[i] = val
        bit[i] += val
        j = i + (i & -i)
        if j <= N:
            bit[j] += bit[i]
            
    results = []
    # クエリの処理
    for _ in range(Q):
        query_type = next(it)
        if query_type == '1':
            # タイプ 1: LからRまでの合計を求める
            L = int(next(it))
            R = int(next(it))
            
            res = 0
            # Rまでの累積和を計算
            idx = R
            while idx > 0:
                res += bit[idx]
                idx -= idx & -idx
            
            # (L-1)までの累積和を引く
            idx = L - 1
            while idx > 0:
                res -= bit[idx]
                idx -= idx & -idx
                
            results.append(str(res))
        else:
            # タイプ 2: 店舗Xの売上をVに更新する
            X = int(next(it))
            V = int(next(it))
            
            # 差分を計算してBITを更新
            diff = V - S[X]
            S[X] = V
            idx = X
            while idx <= N:
                bit[idx] += diff
                idx += idx & -idx
                
    # 結果を一括で出力
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。