概要

この問題は、複数の店舗の売上情報を管理し、区間和の取得と一点更新の操作を高速に処理するものです。

考察

この問題では以下の2種類のクエリを処理する必要があります。

1. 区間 \([L, R]\) の売上額の合計を求める（区間和）
2. 店舗 \(X\) の売上額を新しい値 \(V\) に更新する（一点更新）

素朴な方法として、毎回区間和を愚直に計算することもできますが、その場合1回の区間和クエリで最大 \(O(N)\) かかり、全体で \(O(Q \times N)\) となり、制約 \(N, Q \leq 2 \times 10^5\) のもとでは時間内に処理できません（TLE）。

そこで、区間和の取得と一点更新を効率的に行えるデータ構造「Binary Indexed Tree（BIT）」または「Fenwick Tree」というテクニックを使用します。BIT を使うことで、どちらの操作も \(O(\log N)\) で行え、全体で \(O(Q \log N)\) で処理可能です。

また、BIT は1-indexedで管理するのが一般的なので、配列のインデックスに注意しながら実装する必要があります。

アルゴリズム

Binary Indexed Tree（BIT） を使用して、以下の処理を行います。

初期化フェーズ

• 各店舗の初期売上額 \(S_i\) を BIT に追加します。これは各要素に対して update を行うことで実現できます。

クエリ処理

• クエリ1（区間和）：
  • BIT の range_sum(L, R) メソッドを呼び出し、区間 \([L, R]\) の和を取得して出力します。
• クエリ2（一点更新）：
  • まず変更前の値 \(S[X-1]\) と新しい値 \(V\) の差分 \(delta = V - S[X-1]\) を求めます。
  • BIT 上で update(X, delta) を行い、BIT の値を更新します。
  • 配列 \(S\) も実際に更新しておきます。

BIT の内部では、以下のような操作を行っています：

• update(idx, delta)：位置 idx に値 delta を加算（実際には差分を加算）
• prefix_sum(idx)：位置 \(1\) から idx までの累積和を取得
• range_sum(l, r)：区間 \([l, r]\) の和を prefix_sum(r) - prefix_sum(l - 1) で求める

計算量

• 時間計算量: \(O((N + Q) \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• BIT は1-indexedで扱うので、配列の添字に注意（例：店舗 \(X\) は BIT 内では X として扱う）
• 売上額の更新時は「差分」を BIT に加えることで効率的に更新できる
• Python では sys.stdin.readline を使うことで入力速度を向上させる

ソースコード

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)

---

この解説は qwen3-coder-480b によって生成されました。