Overview

This problem involves managing sales information for multiple stores and efficiently processing range sum queries and point update operations.

Analysis

In this problem, we need to handle the following two types of queries:

1. Find the total sales amount in the interval \([L, R]\) (range sum)
2. Update the sales amount of store \(X\) to a new value \(V\) (point update)

A naive approach would be to compute the range sum directly each time, but in that case, a single range sum query takes up to \(O(N)\), resulting in \(O(Q \times N)\) overall. Under the constraints \(N, Q \leq 2 \times 10^5\), this cannot be processed within the time limit (TLE).

Therefore, we use a data structure called Binary Indexed Tree (BIT), also known as Fenwick Tree, which can efficiently perform both range sum queries and point updates. By using a BIT, both operations can be performed in \(O(\log N)\), allowing the entire process to run in \(O(Q \log N)\).

Additionally, since BIT is typically managed with 1-indexed arrays, care must be taken with array indices during implementation.

Algorithm

We use a Binary Indexed Tree (BIT) to perform the following operations.

Initialization Phase

• Add each store’s initial sales amount \(S_i\) to the BIT. This can be achieved by calling update for each element.

Query Processing

• Query 1 (Range Sum):
  • Call the BIT’s range_sum(L, R) method to obtain the sum of the interval \([L, R]\) and output it.
• Query 2 (Point Update):
  • First, compute the difference \(delta = V - S[X-1]\) between the previous value \(S[X-1]\) and the new value \(V\).
  • Perform update(X, delta) on the BIT to update its values.
  • Also update the array \(S\) accordingly.

Internally, the BIT performs the following operations: - update(idx, delta): Adds the value delta to position idx (effectively adding the difference) - prefix_sum(idx): Retrieves the cumulative sum from position \(1\) to idx - range_sum(l, r): Computes the sum of the interval \([l, r]\) as prefix_sum(r) - prefix_sum(l - 1)

Complexity

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

Implementation Notes

• Since BIT uses 1-indexed arrays, pay attention to array indices (e.g., store \(X\) is treated as X within the BIT)

• When updating sales amounts, efficiently update the BIT by adding the “difference”

• In Python, use sys.stdin.readline to improve input reading speed

  Source Code

import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & (-idx)
    
    def prefix_sum(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & (-idx)
        return res
    
    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

N, Q = map(int, input().split())
S = list(map(int, input().split()))

bit = BIT(N)
for i in range(N):
    bit.update(i + 1, S[i])

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, L, R = query
        print(bit.range_sum(L, R))
    else:
        _, X, V = query
        delta = V - S[X - 1]
        S[X - 1] = V
        bit.update(X, delta)

---

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