概要

\(N\) 個の貯金箱に対して、「範囲 \(L\) から \(R\) に一律で金額を加算する」操作と、「特定の貯金箱 \(P\) の現在の金額を確認する」操作を効率的に行う問題です。

考察

まず、素直な方法（愚直なシミュレーション）を考えてみます。 種類 1 の操作（範囲加算）が呼ばれるたびに、ループを使って \(L\) 番目から \(R\) 番目までの貯金箱に加算を行うと、1 回の操作に最大で \(O(N)\) の時間がかかります。 操作の回数は \(Q\) 回であるため、最悪の場合の計算量は \(O(NQ)\) となります。本問題の制約（\(N, Q \leq 2 \times 10^5\)）では、\(NQ\) は最大で \(4 \times 10^{10}\) 程度になり、実行時間制限に間に合いません。

そこで、「範囲更新」と「一点取得」を高速に行えるデータ構造が必要になります。 この問題は、「差分」を管理するという考え方を用いることで、効率的に解くことができます。

通常、Binary Indexed Tree (BIT) は「一点更新・区間和取得」に使われますが、差分配列の考え方を組み合わせることで、以下のように役割を逆転させることができます。 - 範囲更新 \([L, R]\) に \(X\) を加算: 差分を管理する配列の \(L\) 番目に \(+X\)、\(R+1\) 番目に \(-X\) を加算する（一点更新 2 回）。 - 一点取得 \(P\) の値を計算: 差分配列の \(1\) 番目から \(P\) 番目までの累積和を求める（区間和取得 1 回）。

これに初期状態の金額 \(A_P\) を足すことで、現在の金額を求めることができます。

アルゴリズム

Binary Indexed Tree (BIT) / Fenwick Tree

BIT は、累積和の計算と要素の更新を共に \(O(\log N)\) で行えるデータ構造です。

1. 初期化:
   • 各貯金箱の初期金額 \(A_i\) を配列に保持します。
   • 加算分を管理するための BIT をサイズ \(N+1\) で作成し、すべて \(0\) で初期化します。
2. 種類 1（範囲加算）:
   • 貯金箱 \(L\) から \(R\) に \(X\) 円加算する場合、BIT に対して add(L, X) と add(R + 1, -X) を行います。
3. 種類 2（一点取得）:
   • 貯金箱 \(P\) の現在の金額を知りたい場合、BIT で \(1\) から \(P\) までの累積和を求めます。これを query(P) とすると、求める答えは \(A_P + query(P)\) となります。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 各クエリに対して \(O(\log N)\) で処理でき、初期入力の読み込みと BIT の操作を合わせても十分高速です。
• 空間計算量: \(O(N)\)
  • 初期値を格納する配列 \(A\) と、BIT 用の配列で \(O(N)\) のメモリを使用します。

実装のポイント

• 1-indexed の扱い: BIT は通常 1-indexed で実装されるため、入力された \(L, R, P\) をそのままインデックスとして利用できます。

• 高速な入出力: Python の場合、入力データが多い（\(4 \times 10^5\) 行以上）ため、sys.stdin.read().split() や sys.stdout.write を利用して入出力を高速化することが推奨されます。

• 累積和の意味: 差分配列に対する累積和が、その地点における「これまでの加算の合計」になるという性質を理解することが重要です。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白で分割してイテレータを作成することで高速に処理します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # 貯金箱の数 N と操作の回数 Q を取得
    N = int(next(it))
    Q = int(next(it))
    
    # 各貯金箱の初期金額 A を取得
    # A[0] が貯金箱 1、A[N-1] が貯金箱 N に対応します
    A = [int(next(it)) for _ in range(N)]
    
    # 範囲更新・一点取得を効率的に行うための Binary Indexed Tree (BIT)
    # bit[i] は差分配列の手法を用いて、各貯金箱への加算額を管理します
    bit = [0] * (N + 1)
    
    results = []
    for _ in range(Q):
        # 操作の種類を取得
        query_type = next(it)
        
        if query_type == '1':
            # 種類 1：貯金箱 L から R までに X 円を追加
            l = int(next(it))
            r = int(next(it))
            x = int(next(it))
            
            # BIT を用いた範囲更新（差分配列の考え方）
            # インデックス l 以降に x を加算
            curr = l
            while curr <= N:
                bit[curr] += x
                curr += curr & -curr
            
            # インデックス r + 1 以降から x を減算
            curr = r + 1
            while curr <= N:
                bit[curr] -= x
                curr += curr & -curr
        else:
            # 種類 2：貯金箱 P の現在の金額を確認
            p = int(next(it))
            
            # BIT から位置 p における累積加算額を取得
            update_sum = 0
            curr = p
            while curr > 0:
                update_sum += bit[curr]
                curr -= curr & -curr
            
            # 初期金額に累積加算額を足して結果を保存
            results.append(str(A[p-1] + update_sum))
            
    # すべての確認操作の結果をまとめて出力
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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