Overview

Given \(N\) piggy banks, we need to efficiently handle two types of operations: “add a uniform amount to all piggy banks in the range \(L\) to \(R\)” and “query the current amount in a specific piggy bank \(P\).”

Analysis

First, let’s consider a straightforward approach (brute-force simulation). If we use a loop to add to piggy banks from index \(L\) to \(R\) each time a type 1 operation (range addition) is called, a single operation takes up to \(O(N)\) time. Since there are \(Q\) operations, the worst-case time complexity is \(O(NQ)\). Under the constraints of this problem (\(N, Q \leq 2 \times 10^5\)), \(NQ\) can be as large as approximately \(4 \times 10^{10}\), which will not fit within the time limit.

Therefore, we need a data structure that can efficiently perform “range updates” and “point queries”. This problem can be solved efficiently using the concept of managing “differences”.

Normally, a Binary Indexed Tree (BIT) is used for “point updates and range sum queries,” but by combining it with the difference array technique, we can reverse the roles as follows: - Range update: add \(X\) to \([L, R]\): Add \(+X\) to position \(L\) and \(-X\) to position \(R+1\) in the difference array (two point updates). - Point query: compute the value at \(P\): Compute the prefix sum from position \(1\) to \(P\) in the difference array (one range sum query).

By adding the initial amount \(A_P\) to this result, we can obtain the current amount.

Algorithm

Binary Indexed Tree (BIT) / Fenwick Tree

A BIT is a data structure that can perform both prefix sum computation and element updates in \(O(\log N)\).

1. Initialization:
   • Store the initial amount \(A_i\) of each piggy bank in an array.
   • Create a BIT of size \(N+1\) for managing the added amounts, initialized to all \(0\)s.
2. Type 1 (Range Addition):
   • To add \(X\) yen to piggy banks \(L\) through \(R\), perform add(L, X) and add(R + 1, -X) on the BIT.
3. Type 2 (Point Query):
   • To find the current amount in piggy bank \(P\), compute the prefix sum from \(1\) to \(P\) using the BIT. Denoting this as query(P), the answer is \(A_P + query(P)\).

Complexity

• Time Complexity: \(O((N + Q) \log N)\)
  • Each query is processed in \(O(\log N)\), and combined with reading the initial input and BIT operations, this is sufficiently fast.
• Space Complexity: \(O(N)\)
  • The array \(A\) for storing initial values and the BIT array use \(O(N)\) memory.

Implementation Notes

• 1-indexed handling: Since BITs are typically implemented as 1-indexed, the input values \(L, R, P\) can be used directly as indices.

• Fast I/O: In Python, since the input data is large (over \(4 \times 10^5\) lines), it is recommended to use sys.stdin.read().split() and sys.stdout.write to speed up I/O.

• Meaning of prefix sums: It is important to understand the property that the prefix sum over the difference array gives the “total of all additions up to that point.”

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.