Overview

This problem requires efficiently processing two types of queries on an array: “find the sum of a range” and “update a single element’s value.” This can be solved efficiently using a Fenwick Tree (Binary Indexed Tree).

Analysis

Problems with the Naive Approach

First, let’s consider a simple method.

• Range sum query: Add up values from store \(L\) to \(R\) sequentially → \(O(N)\)
• Update query: Directly modify the array value → \(O(1)\)

With this method, range sum queries can be called up to \(Q = 2 \times 10^5\) times, and each query requires up to \(N = 2 \times 10^5\) additions, resulting in \(O(NQ) = 4 \times 10^{10}\) total calculations. This would result in TLE (Time Limit Exceeded).

Problems with Using Prefix Sums

Using prefix sums allows range sums to be computed in \(O(1)\), but each point update requires updating the entire prefix sum array, making updates cost \(O(N)\).

Solution: Fenwick Tree

Using a Fenwick Tree (BIT: Binary Indexed Tree), both operations can be performed in \(O(\log N)\).

Algorithm

What is a Fenwick Tree?

A Fenwick Tree is a data structure that efficiently performs the following two operations:

1. Point addition: Add a value to the \(i\)-th element of the array
2. Prefix sum: Find the sum from the \(1\)-st to the \(i\)-th element of the array

How It Works (Simple Explanation)

A Fenwick Tree manages array elements as “values summarized by intervals.” Each index \(i\) holds the sum of several elements before it. The range to summarize is determined by the lowest set bit when \(i\) is represented in binary.

For example, when \(i = 6 = (110)_2\), the lowest 1 bit represents \(2\), so position \(6\) stores the sum of \(2\) elements (indices \(5, 6\)).

Application to This Problem

1. Initialization: Register each store’s sales amount into the Fenwick Tree
2. Query 1 (Range sum): Calculate using \(\text{sum}(R) - \text{sum}(L-1)\)
3. Query 2 (Update): Add the difference \(V - S[X]\) between the new value \(V\) and the current value \(S[X]\) to the Fenwick Tree

Example: N=5, initial values [10, 20, 30, 40, 50]
Query "1 2 4" → Sum of stores 2~4 = 20 + 30 + 40 = 90
Query "2 3 100" → Update store 3's sales to 100
Query "1 2 4" → Sum of stores 2~4 = 20 + 100 + 40 = 160

Complexity

• Time Complexity: \(O((N + Q) \log N)\)

  • Initialization: \(O(N \log N)\) (\(N\) add operations)
  • Each query: \(O(\log N)\) (\(Q\) queries total)

• Space Complexity: \(O(N)\)

  • Array for the Fenwick Tree and an array to hold the current sales amounts

Implementation Notes

1. Update using differences: For Query 2, instead of “replacing with the new value,” we “add the difference.” Therefore, we separately maintain the current sales amount \(S[X]\), calculate \(V - S[X]\), and then add it to the Fenwick Tree.

2. 1-indexed: Fenwick Trees are typically implemented as 1-indexed. Since store numbers start from 1, this maps directly.

3. Fast I/O: Since \(N, Q\) can be as large as \(2 \times 10^5\), we use sys.stdin.buffer.read() for bulk input and '\n'.join() to output results together for faster execution.

   Source Code

import sys

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
    
    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    S = [0] * (N + 1)
    for i in range(1, N + 1):
        S[i] = int(input_data[idx]); idx += 1
    
    ft = FenwickTree(N)
    for i in range(1, N + 1):
        ft.add(i, S[i])
    
    results = []
    for _ in range(Q):
        query_type = int(input_data[idx]); idx += 1
        if query_type == 1:
            L = int(input_data[idx]); idx += 1
            R = int(input_data[idx]); idx += 1
            results.append(ft.range_sum(L, R))
        else:
            X = int(input_data[idx]); idx += 1
            V = int(input_data[idx]); idx += 1
            delta = V - S[X]
            S[X] = V
            ft.add(X, delta)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.