概要

この問題は、貯金箱の金額を管理しながら範囲更新と点クエリを効率的に処理する問題です。

考察

素朴なアプローチでは、種類1の操作（範囲更新）をそのまま実装すると、毎回 \(R-L+1\) 個の貯金箱を更新する必要があります。最悪の場合、操作回数 \(Q\) と範囲の長さがともに大きいと、計算量が \(O(NQ)\) となり、制約条件 \(N, Q \leq 2 \times 10^5\) では確実に時間制限に間に合いません。

そこで、範囲更新を効率的に行うデータ構造が必要になります。この問題では「区間加算・点取得」を高速に処理できるFenwick Tree（Binary Indexed Tree）を使用します。Fenwick Treeは、区間への加算操作を差分で管理することで、点クエリを \(O(\log N)\)、範囲更新も \(O(\log N)\) で処理できます。

アルゴリズム

Fenwick Treeを用いた「区間加算・点取得」の手法を採用します。具体的には：

1. 初期化: 各貯金箱の初期金額 \(A_i\) を別途配列に保持します
2. 範囲更新: 区間 \([L, R]\) に \(X\) 円を加算する場合：
   • 位置 \(L\) に \(+X\) を加算
   • 位置 \(R+1\) に \(-X\) を加算（\(R+1\) が配列範囲内の場合）
3. 点取得: 貯金箱 \(P\) の金額を求める場合：
   • 初期金額 \(A[P]\) に、Fenwick Treeの位置 \(P\) までの累積和を加算

この手法は、Fenwick Treeが実際には「各位置までの累積加算量」を管理していることに基づきます。位置 \(P\) までの累積和を求めることで、\(P\) に加算された総額が得られます。

計算量

• 時間計算量: \(O(Q \log N)\)
  • 各クエリを \(O(\log N)\) で処理
• 空間計算量: \(O(N)\)
  • Fenwick Treeと初期金額配列の分

実装のポイント

1. Fenwick Treeの実装では、インデックスを1-indexedで扱う

2. 範囲更新時に \(R+1\) が配列範囲を超えないよう注意する

3. 入力データが大きいため、sys.stdin.read()で一括読み込みを行う

4. 出力もリストに蓄えて最後に一括出力する

   ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    q = int(next(it))
    A = [0] * (n + 1)
    for i in range(1, n + 1):
        A[i] = int(next(it))
    
    fenw = [0] * (n + 2)
    
    def update(i, val):
        while i <= n:
            fenw[i] += val
            i += i & -i
            
    def query(i):
        s = 0
        while i > 0:
            s += fenw[i]
            i -= i & -i
        return s
            
    output_lines = []
    for _ in range(q):
        t = next(it)
        if t == '1':
            L = int(next(it))
            R = int(next(it))
            X = int(next(it))
            update(L, X)
            if R < n:
                update(R + 1, -X)
        else:
            P = int(next(it))
            res = A[P] + query(P)
            output_lines.append(str(res))
            
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。