Overview

This is a problem where you need to efficiently process range additions (deposits) on an interval \([L,R]\) and point queries (balance checks) at a single point \(P\).

Analysis

A naive approach of “updating all positions from \(L\) to \(R\) for each type 1 operation” takes up to \(O(N)\) per operation, leading to a worst case of \(O(NQ)\) (with both being up to \(2\times 10^5\), this is approximately \(4\times 10^{10}\)), which will result in a time limit exceeded.

The key insight is that range additions can be represented using a difference array.
By maintaining an array \(B\) as the “difference of additions”:

• Adding \(X\) to the interval \([L,R]\)
  \(\Rightarrow B_L += X,\; B_{R+1} -= X\)

The total value actually added to each position \(P\) can be obtained as the prefix sum of \(B\): \(\sum_{i=1}^{P} B_i\).

In other words, what we need is: - Point updates on \(B\) (at the two positions \(B_L\) and \(B_{R+1}\)) - Prefix sums of \(B\) (\(\sum_{i=1}^{P} B_i\))

This can be efficiently handled using a Fenwick Tree (BIT).

Concrete example: - \(N=5\), operation “add \(+3\) to \([2,4]\)”
The difference is \(B_2 += 3,\; B_5 -= 3\) (\(R+1=5\)) - The prefix sums are then:
\(P=1:0,\; P=2:3,\; P=3:3,\; P=4:3,\; P=5:0\)
Thus we can see that only positions 2 through 4 have been increased by +3.

Algorithm

1. Keep the initial array \(A\) as-is (initial balances).
2. Manage the difference array \(B\) with a Fenwick Tree (initially all 0).
3. Process queries:
   • Type 1 (range addition):
     
     • add(L, X) (\(B_L += X\))
     • add(R+1, -X) (\(B_{R+1} -= X\))
   • Type 2 (point query):
     
     • The added amount is sum(P) (\(\sum_{i=1}^{P} B_i\))
     • Output the answer as \(A_P + \text{sum}(P)\)

The Fenwick Tree supports: - add(i, x): Add \(x\) to position \(i\) (\(O(\log N)\)) - sum(i): Prefix sum from \(1..i\) (\(O(\log N)\))

Complexity

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

Implementation Notes

• It is standard practice to implement the Fenwick Tree as 1-indexed (in the code, query indices are used as-is).

• Since \(R+1\) in type 1 updates can become \(N+1\), the Fenwick Tree is allocated with size N+1 to safely perform add(R+1, -X).

• Since the input can be up to \(2\times 10^5\) lines, sys.stdin.buffer.read() is used for bulk reading to speed up I/O.

  Source Code

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

This editorial was generated by gpt-5.2-high.