Overview

This problem requires efficiently handling range updates and point queries while managing the amounts in piggy banks.

Analysis

In a naive approach, directly implementing type 1 operations (range updates) would require updating \(R-L+1\) piggy banks each time. In the worst case, when both the number of operations \(Q\) and the range length are large, the time complexity becomes \(O(NQ)\), which will certainly exceed the time limit under the constraints \(N, Q \leq 2 \times 10^5\).

Therefore, we need a data structure that can perform range updates efficiently. In this problem, we use a Fenwick Tree (Binary Indexed Tree), which can efficiently handle “range addition and point query” operations. By managing range addition operations using differences, the Fenwick Tree can process point queries in \(O(\log N)\) and range updates also in \(O(\log N)\).

Algorithm

We adopt the “range addition and point query” technique using a Fenwick Tree. Specifically:

1. Initialization: Store the initial amount \(A_i\) of each piggy bank in a separate array
2. Range update: To add \(X\) yen to the interval \([L, R]\):
   • Add \(+X\) at position \(L\)
   • Add \(-X\) at position \(R+1\) (if \(R+1\) is within the array bounds)
3. Point query: To find the amount in piggy bank \(P\):
   • Add the prefix sum up to position \(P\) in the Fenwick Tree to the initial amount \(A[P]\)

This technique is based on the fact that the Fenwick Tree actually manages “the cumulative addition amount up to each position.” By computing the prefix sum up to position \(P\), we obtain the total amount added to \(P\).

Complexity

• Time complexity: \(O(Q \log N)\)
  • Each query is processed in \(O(\log N)\)
• Space complexity: \(O(N)\)
  • For the Fenwick Tree and the initial amount array

Implementation Notes

1. In the Fenwick Tree implementation, use 1-indexed indexing

2. Be careful that \(R+1\) does not exceed the array bounds during range updates

3. Since the input data is large, read all input at once using sys.stdin.read()

4. Also accumulate output in a list and print everything at once at the end

   Source Code

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

This editorial was generated by deepseekv3.