Overview

In this problem, we need to efficiently perform range addition and point query operations on multiple piggy banks.

Approach

The piggy banks have initial values, and then two types of operations are repeated: “add the same amount to all piggy banks in a certain range” and “answer the current amount in a specific piggy bank.”

If we naively process this using an array, each range addition takes \(O(N)\), resulting in a worst case of \(O(QN)\) overall, which is too slow given the constraints (up to \(4 \times 10^{10}\) computations required).

Therefore, we use a BIT (Fenwick Tree), a data structure that can efficiently handle both range addition and point query. However, a BIT is typically designed for “point update and prefix sum query.” To use it in reverse, we apply the difference array technique.

Specifically, instead of managing array \(A\) directly, we manage its difference array \(D\) in the BIT: - \(D[1] = A[1]\) - \(D[i] = A[i] - A[i-1]\) (for \(i \geq 2\))

Then, \(A[P]\) can be computed as \(D[1] + D[2] + \cdots + D[P] = \sum_{i=1}^{P} D[i]\). This can be efficiently calculated using the BIT’s prefix sum functionality.

The operation of adding \(X\) to the range \([L, R]\) can be expressed on the difference array as follows: - \(D[L] \mathrel{+}= X\) - \(D[R+1] \mathrel{-}= X\)

This transforms a range update into two point updates, which can be efficiently processed on the BIT.

Algorithm

1. Read input and construct the initial array \(A[1..N]\).
2. Create the difference array \(D\) and insert it into the BIT:
   • \(D[1] = A[1]\)
   • \(D[i] = A[i] - A[i-1]\) (for \(i = 2, 3, ..., N\))
3. For each operation:
   • Type 1 (range addition): Perform \(D[L] \mathrel{+}= X\) and \(D[R+1] \mathrel{-}= X\) on the BIT.
   • Type 2 (point query): Use the BIT’s prefix sum function to compute \(\sum_{i=1}^{P} D[i]\) and output it as the answer.

Complexity

• Time complexity: \(O(Q \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since BIT uses 1-indexed arrays, it is easier to maintain consistency by also using 1-indexed arrays.
• When performing range addition, check whether \(R+1\) is within bounds (boundary handling).
• Correctly insert the initial differences into the BIT (the first element needs special treatment for correct behavior).

## Source Code

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

This editorial was generated by qwen3-coder-480b.