Overview

This is a problem where we process \(Q\) operations of “range sum query” and “point update” on a sales array. To perform each operation efficiently, we use a Fenwick Tree (Binary Indexed Tree).

Analysis

In this problem, we repeatedly process the following 2 types of queries:

• Type 1: Total sales (range sum) over \([L, R]\)
• Type 2: Change the sales of store \(X\) to \(V\) (point update)

Naively, if we compute \(S_L + S_{L+1} + \cdots + S_R\) directly for each Type 1 query, a single query takes up to \(O(N)\). In the worst case \(Q=2\times10^5\), so the total becomes \(O(NQ)\), which is too slow to finish in time (TLE).

On the other hand, if we precompute a prefix sum, we can answer range sum queries in \(O(1)\), but rebuilding the prefix sum after each Type 2 update costs \(O(N)\), which is also too slow.

Therefore, we need a data structure that can perform both “point update” and “prefix sum query” in \(O(\log N)\). The canonical data structure that satisfies this is the Fenwick Tree.

Algorithm

A Fenwick Tree (Binary Indexed Tree) is a data structure that efficiently supports the following operations:

• add(i, x): Add \(x\) to the \(i\)-th element of the array (incremental addition)
• sum(i): Retrieve \(S_1 + S_2 + \cdots + S_i\) (prefix sum from 1 to i)

The range sum can be computed using prefix sums as: $\( \sum_{k=L}^{R} S_k = \mathrm{sum}(R) - \mathrm{sum}(L-1) \)$

Also, since the update in this problem is “change \(S_X\) to \(V\)”, we only add the difference to the Fenwick Tree. If we maintain the current value as \(A[X]\), we compute: $\( \Delta = V - A[X] \)\( and perform `add(X, Δ)`. After that, we update \)A[X] = V$.

Concrete Example

When \(S = [3, 1, 4, 1, 5]\), the sum over \([2,4]\) is: - \(\mathrm{sum}(4)=3+1+4+1=9\) - \(\mathrm{sum}(1)=3\) - Therefore \(9-3=6\)

When updating store 3 from \(4 \rightarrow 10\), the difference is \(\Delta = 10-4=6\), so we call add(3, 6) to maintain consistency.

Complexity

• Time complexity: Initial construction \(O(N\log N)\), each query \(O(\log N)\), so overall \(O((N+Q)\log N)\)
• Space complexity: \(O(N)\) for the Fenwick Tree and the current value array

Implementation Notes

• The Fenwick Tree is cleanest when implemented as 1-indexed (indices starting from \(1\)). In the code, the array size is set to \(N+1\) accordingly.

• For “updating the value to \(V\)”, it is important not to assign directly, but to compute the difference \(\Delta=V-A[X]\) and call add.

• Since the input is large, reading all at once with sys.stdin.buffer.read() and accumulating output in an array to print all at once at the end improves performance.

  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 = [0] * (N + 1)
    fw = Fenwick(N)
    for i in range(1, N + 1):
        v = next(it)
        A[i] = v
        fw.add(i, v)

    out = []
    for _ in range(Q):
        t = next(it)
        if t == 1:
            L = next(it)
            R = next(it)
            out.append(str(fw.sum(R) - fw.sum(L - 1)))
        else:
            X = next(it)
            V = next(it)
            delta = V - A[X]
            if delta:
                fw.add(X, delta)
                A[X] = V

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.