概要

区間 \([L,R]\) への一括加算（入金）と、1点 \(P\) の値の取得（残高確認）を、各操作あたり高速に処理する問題です。

考察

素朴に「種類1のたびに \(L\) から \(R\) をすべて更新」すると、1回の操作で最大 \(O(N)\) かかり、最悪で \(O(NQ)\)（\(2\times 10^5\) 同士なので約 \(4\times 10^{10}\)）となって時間切れになります。

重要な気づきは、区間加算は差分配列で表せるということです。
配列 \(B\) を「加算の差分」として管理し、

• 区間 \([L,R]\) に \(X\) を加える
  \(\Rightarrow B_L += X,\; B_{R+1} -= X\)

とすると、各位置 \(P\) に実際に加算される合計値は
\(B\) の 前からの累積和 \(\sum_{i=1}^{P} B_i\) で求まります。

つまり、必要なのは - \(B\) への 1点加算（\(B_L\) と \(B_{R+1}\) の2箇所） - \(B\) の 前方累積和（\(\sum_{i=1}^{P} B_i\)）

であり、これは Fenwick Tree（BIT）で高速に処理できます。

具体例： - \(N=5\)、操作「\([2,4]\) に \(+3\)」
差分は \(B_2 += 3,\; B_5 -= 3\)（\(R+1=5\)） - このとき累積和は
\(P=1:0,\; P=2:3,\; P=3:3,\; P=4:3,\; P=5:0\)
よって 2〜4 だけ +3 されていることが分かります。

アルゴリズム

1. 初期配列 \(A\) はそのまま保持する（初期残高）。
2. 差分配列 \(B\) を Fenwick Tree で管理する（最初はすべて 0）。
3. クエリを処理する：
   • 種類1（区間加算）:
     
     • add(L, X)（\(B_L += X\)）
     • add(R+1, -X)（\(B_{R+1} -= X\)）
   • 種類2（点取得）:
     
     • 追加分は sum(P)（\(\sum_{i=1}^{P} B_i\)）
     • 答えは \(A_P + \text{sum}(P)\) を出力

Fenwick Tree は - add(i, x)：位置 \(i\) に \(x\) を加算（\(O(\log N)\)） - sum(i)：\(1..i\) の累積和（\(O(\log N)\)） を実現します。

計算量

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

実装のポイント

• 1-indexed で Fenwick Tree を実装するのが定石です（コードでもクエリの添字はそのまま使っています）。

• 種類1で更新する \(R+1\) が \(N+1\) になる場合があるため、Fenwick を N+1 サイズで確保し、add(R+1, -X) を安全に行っています。

• 入力が最大 \(2\times 10^5\) 行なので、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 = [next(it) for _ in range(N)]

    fw = Fenwick(N + 1)  # allow R+1 updates up to N+1 safely
    out = []

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

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

if __name__ == "__main__":
    main()

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