Day 006-Q1 | BIT（Fenwick Tree）

問題

長さ $N$ の数列 $A$ があります。以下の $Q$ 個のクエリを処理してください。

1 i x : A[i] に x を加算する（1-indexed）
2 l r : A[l] + A[l+1] + ... + A[r] の合計を出力する（1-indexed）

入力形式

N Q
A[1] A[2] ... A[N]
クエリ1
クエリ2
...

制約

$1 \le N \le 2 \times 10^5$

$1 \le Q \le 2 \times 10^5$

$0 \le A[i] \le 10^9$

$1 \le i \le N,\ -10^9 \le x \le 10^9$

$1 \le l \le r \le N$

入出力例

入力例 1

出力例 1

6
16
12

ヒント (段階的開示)

ヒント1: 方向性

愚直に配列を更新・集計すると $O(N) \times Q$ で TLE になります。高速なデータ構造が必要です。

ヒント2: アプローチ

BIT（Fenwick Tree）は 点更新 $O(\log N)$・区間和クエリ $O(\log N)$ を実現するデータ構造です。配列のビット演算を使って「親ノード」を効率的に求めます。

ヒント3: 誘導

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, x):  # 1-indexed
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)  # 最下位ビット分を足して「親」へ

    def sum(self, i):  # [1, i] の累積和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)  # 最下位ビット分を引いて「親」へ
        return s

    def query(self, l, r):  # [l, r] の区間和
        return self.sum(r) - self.sum(l - 1)

模範解答 (Python)

import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, x):
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def query(self, l, r):
        return self.sum(r) - self.sum(l - 1)

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    bit = BIT(N)
    for i, a in enumerate(A):
        bit.add(i + 1, a)  # 1-indexed

    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            _, i, x = query
            bit.add(i, x)
        else:
            _, l, r = query
            print(bit.query(l, r))

main()

Step-by-Step 解説

1BIT の構造を理解する
BIT は 1-indexed の配列で、tree[i] は「i の最下位ビット分の区間」の和を保持。例: $N=8$ のとき tree[6] ($110_2$) は A[5]+A[6] の和を保持。

2add（点更新）
i += i & (-i) で「親」へ。例: 3(011) → 4(100) → 8(1000)。i & (-i) は i の最下位ビットを取り出す操作。

3sum（累積和）
i -= i & (-i) で「親」へ。例: 6(110) → 4(100) → 0。

4区間和クエリ
query(l, r) = sum(r) - sum(l-1) で区間 $[l, r]$ の和を $O(\log N)$ で求められる。

よくあるミス

ミス	原因	正しい書き方
0-indexed で実装	BIT は 1-indexed 必須	`bit.add(i+1, a)`
`i & (-i)` を忘れる	ビット演算の意味を理解していない	最下位ビット取得の公式として覚える
初期化を忘れる	初期配列を BIT に登録していない	全要素を `add()` で追加する

Day 006-Q1 — BIT（Fenwick Tree）

問題