概要

この問題では、複数の貯金箱に対して区間加算と一点取得の操作を高速に行う必要があります。

考察

貯金箱の金額は初期値を持ち、その後「ある区間の全ての貯金箱に同じ金額を加える」という操作と、「特定の貯金箱の現在の金額を答える」という操作が繰り返されます。

もし素朴に配列を使って処理すると、区間加算に \(O(N)\) かかり、全体で最悪 \(O(QN)\) となり、制約が大きいため間に合いません（最大で \(4 \times 10^{10}\) 回の計算が必要）。

そこで、区間加算と一点取得の両方を効率的に行えるデータ構造である「BIT（Fenwick Tree）」を活用します。ただし、BIT は通常「一点加算・区間和」を得意とします。これを逆に使うために、差分を管理するテクニックを使います。

具体的には、配列 \(A\) の代わりにその差分配列 \(D\) をBITで管理します： - \(D[1] = A[1]\) - \(D[i] = A[i] - A[i-1]\) （\(i \geq 2\)）

このとき、\(A[P]\) は \(D[1] + D[2] + \cdots + D[P] = \sum_{i=1}^{P} D[i]\) として求められます。これはBITの区間和機能で高速に計算可能です。

区間 \([L, R]\) に \(X\) を加える操作は、差分配列上では以下のように表現できます： - \(D[L] \mathrel{+}= X\) - \(D[R+1] \mathrel{-}= X\)

これにより、区間更新を2回の一点更新に変換でき、BIT上で効率的に処理できます。

アルゴリズム

1. 入力を読み込み、初期配列 \(A[1..N]\) を構築。
2. 差分配列 \(D\) を作成し、BITに挿入：
   • \(D[1] = A[1]\)
   • \(D[i] = A[i] - A[i-1]\) （\(i = 2, 3, ..., N\)）
3. 各操作について：
   • 種類1（区間加算）：BIT上で \(D[L] \mathrel{+}= X\), \(D[R+1] \mathrel{-}= X\) を行う。
   • 種類2（一点取得）：BITの区間和関数を使って \(\sum_{i=1}^{P} D[i]\) を取得し、答えとして出力。

計算量

• 時間計算量: \(O(Q \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• BITは1-indexedで扱う必要があるため、配列も1-indexedで持つと整合性が取りやすい。
• 区間加算の際に \(R+1\) が範囲内かどうかチェックすること（境界処理）。
• 初期値の差分を正しくBITに挿入する（最初の要素だけ特別扱いしないと正しく動作しない）。

## ソースコード

```python
import sys
from itertools import accumulate

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def add(self, i, x):
        while i <= self.n:
            self.tree[i] += x
            i += i & -i
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(data[idx])
        idx += 1
    
    # 差分BITを使用して区間加算、一点取得を行う
    bit = BIT(N)
    
    # 初期値を処理: A[i] を i番目にセット
    # 実際には差分を管理するので、A[i] - A[i-1] をBITに追加
    prev = 0
    for i in range(1, N + 1):
        bit.add(i, A[i] - prev)
        prev = A[i]
    
    results = []
    for _ in range(Q):
        t = int(data[idx])
        idx += 1
        if t == 1:
            L = int(data[idx])
            idx += 1
            R = int(data[idx])
            idx += 1
            X = int(data[idx])
            idx += 1
            # 区間[L, R]にXを加算
            bit.add(L, X)
            if R + 1 <= N:
                bit.add(R + 1, -X)
        else:
            P = int(data[idx])
            idx += 1
            # P番目の値を取得
            res = bit.sum(P)
            results.append(str(res))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。