Overview

This is a problem where we need to efficiently process “uniform addition over a range” and “retrieval of a single point’s value” for \(N\) piggy banks. It can be solved efficiently using the difference array technique with a BIT (Binary Indexed Tree).

Analysis

Problems with the Naive Approach

If we naively implement the Type 1 operation (range addition), we need to add the value one by one to each piggy bank from \(L\) to \(R\), which takes \(O(N)\) per operation. Since there are \(Q\) operations, the worst case is \(O(NQ)\). When \(N, Q\) are at most \(2 \times 10^5\), this requires approximately \(4 \times 10^{10}\) computations, resulting in TLE (Time Limit Exceeded).

Key Insight: Difference Array

In situations where we want to uniformly add \(X\) to a range \([L, R]\) and retrieve the value at a single point \(P\), the difference array technique is effective.

We prepare a difference array \(D\) and represent the operation of adding \(X\) to the range \([L, R]\) as follows:

• Add \(+X\) to \(D[L]\)
• Add \(-X\) to \(D[R+1]\)

Then, the total value added at position \(P\) is \(D[1] + D[2] + \cdots + D[P]\) (= the prefix sum of \(D\) up to \(P\)).

Concrete example: For \(N = 5\), adding \(+3\) to the range \([2, 4]\)

Index	1	2	3	4	5
Changes in \(D\)	0	+3	0	0	-3
Prefix sum	0	3	3	3	0

Indeed, \(3\) is added only to positions \(2, 3, 4\).

Further Optimization: Using BIT

Computing the prefix sum of the difference array in \(O(N)\) each time is still too slow. By using a BIT (Binary Indexed Tree / Fenwick Tree), we can perform each of the following operations in \(O(\log N)\):

• Point update: Add a value to \(D[i]\)
• Prefix sum query: Compute \(D[1] + D[2] + \cdots + D[P]\)

Algorithm

1. Store the initial amounts \(A\) as an array.
2. Initialize the BIT as a difference array (all \(0\)s).
3. Process each query:
   • Type 1 (add \(X\) to range \([L, R]\)): On the BIT, add \(+X\) at \(L\) and \(-X\) at \(R+1\).
   • Type 2 (retrieve value at position \(P\)): Output \(A[P] +\) the prefix sum of the BIT up to \(P\).

Complexity

• Time complexity: \(O(N + Q \log N)\)
  • \(O(N)\) for reading the initial array, and \(O(\log N)\) per query for BIT operations
• Space complexity: \(O(N)\)
  • For the initial array and the BIT array

Implementation Notes

• BIT indices are typically 1-indexed. Since the initial array \(A\) is 0-indexed, be careful to shift the index with A[P-1] when processing queries.

• When adding \(-X\) to \(R+1\) in the difference array, if \(R+1 > N\), it falls outside the array, so no addition is needed (the if R + 1 <= N condition in the code).

• Instead of outputting one by one with print, accumulating results in a list and outputting them all at once with sys.stdout.write at the end helps avoid I/O becoming a bottleneck.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # BIT (Binary Indexed Tree) for range update, point query
    # Using two BITs to support range add and point query
    # For range [L, R] add X:
    #   bit.add(L, X), bit.add(R+1, -X)
    # Point query P: prefix sum up to P
    
    bit = [0] * (N + 2)
    
    def update(i, val):
        while i <= N:
            bit[i] += val
            i += i & (-i)
    
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            L = int(line[1])
            R = int(line[2])
            X = int(line[3])
            update(L, X)
            if R + 1 <= N:
                update(R + 1, -X)
        else:
            P = int(line[1])
            out.append(str(A[P - 1] + query(P)))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.