Overview

This problem requires efficiently performing two types of operations: “point updates” that modify specific elements of an array, and “range sum queries” that compute the sum over a specified range.

Analysis

First, let’s consider a naive approach (simulation). - Update query: Simply overwriting a value in the array takes \(O(1)\). - Sum query: Summing from store \(L\) to \(R\) takes \(O(N)\) in the worst case.

Since there are \(Q\) queries, the overall time complexity is \(O(NQ)\). Given the constraints \(N, Q \leq 2 \times 10^5\), this could require up to approximately \(4 \times 10^{10}\) operations in the worst case, which will not fit within the time limit (typically around 2 seconds).

To perform both “point updates” and “range sum queries” efficiently, it is common to use data structures such as a Fenwick Tree (Binary Indexed Tree) or a Segment Tree. With these data structures, both operations can be processed in \(O(\log N)\).

Algorithm

In this solution, we use a Fenwick Tree (BIT), which has a simple implementation and fast constant factors.

What is a Fenwick Tree (BIT)?

It is a data structure that extends the concept of prefix sums. Each node stores the sum of a specific range, enabling the following operations:

1. Prefix sum query: Computes the sum from the \(1\)-st to the \(i\)-th element in \(O(\log N)\).
   • Using this, the sum over the range \([L, R]\) can be obtained as (sum from 1 to R) - (sum from 1 to L-1).
2. Element update: Adds a value to a specific element in \(O(\log N)\).
   • Since this problem requires “replacing a value with \(V\)”, we compute new value - current value and add that difference.

Optimized Initialization

Building a BIT by performing \(N\) additions from an empty state takes \(O(N \log N)\), but the code in this solution uses an \(O(N)\) construction method. By propagating each element’s value to its parent node sequentially, the initialization is performed more efficiently.

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Initial construction takes \(O(N)\), and each query is processed in \(O(\log N)\).
  • When \(N, Q = 2 \times 10^5\), the number of operations is roughly on the order of several million, which is fast enough even in Python.
• Space complexity: \(O(N)\)
  • The array S for managing sales and the BIT array bit use \(O(N)\) memory.

Implementation Details

• Fast I/O: When handling large input in Python, repeatedly calling input() is slow, so we read all input at once using sys.stdin.read().split() and process it with an iterator. Output is also sped up by collecting results and writing them all at once using sys.stdout.write.

• 1-indexed: Due to the bit manipulation nature of Fenwick Trees, starting array indices from \(1\) makes the implementation much cleaner.

• Difference-based update: For query type 2, which requires “setting the value to \(V\)”, the key technique is to maintain the current value S[X] and add the difference V - S[X] to the BIT.

  Source Code

import sys

def solve():
    # データの読み込みを高速化するため、sys.stdin.read().split() を使用して
    # すべての入力を一括で取得し、イテレータに変換します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    N = int(next(it))
    Q = int(next(it))
    
    # 各店舗の現在の売上額を保持する配列 (1-indexed)
    S = [0] * (N + 1)
    # Fenwick Tree (Binary Indexed Tree) の配列 (1-indexed)
    bit = [0] * (N + 1)
    
    # Fenwick Tree を O(N) で初期化
    for i in range(1, N + 1):
        val = int(next(it))
        S[i] = val
        bit[i] += val
        j = i + (i & -i)
        if j <= N:
            bit[j] += bit[i]
            
    results = []
    # クエリの処理
    for _ in range(Q):
        query_type = next(it)
        if query_type == '1':
            # タイプ 1: LからRまでの合計を求める
            L = int(next(it))
            R = int(next(it))
            
            res = 0
            # Rまでの累積和を計算
            idx = R
            while idx > 0:
                res += bit[idx]
                idx -= idx & -idx
            
            # (L-1)までの累積和を引く
            idx = L - 1
            while idx > 0:
                res -= bit[idx]
                idx -= idx & -idx
                
            results.append(str(res))
        else:
            # タイプ 2: 店舗Xの売上をVに更新する
            X = int(next(it))
            V = int(next(it))
            
            # 差分を計算してBITを更新
            diff = V - S[X]
            S[X] = V
            idx = X
            while idx <= N:
                bit[idx] += diff
                idx += idx & -idx
                
    # 結果を一括で出力
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.