Day 097-Q3 — 区間加算・区間和 BIT（Fenwick Tree ×2 のトリック）

2026-07-20 赤色 Master / Phase 8+ ★★★★★★★★★ BIT二重化テクニック

問題

長さ $N$ の数列 $A_1,\dots,A_N$（初期値はすべて $0$）に対して、$Q$ 個のクエリを順に処理せよ。

  • 1 l r x: $A_l,\dots,A_r$ にそれぞれ $x$ を加算する
  • 2 l r: $A_l+\dots+A_r$ を出力する

入力形式

N Q
query_1
:
query_Q

制約

$1 \le N,Q \le 2\times10^5$
$1 \le l \le r \le N$
$|x|\le 10^9$
答えは64bit整数に収まる

入出力例

入力例1

5 4
1 1 3 5
2 1 5
1 2 4 2
2 2 4

出力例1

15
16

1回目の加算後 $[5,5,5,0,0]$ で総和15。2回目の加算後 $[5,7,7,2,0]$ で区間[2,4]の和は $7+7+2=16$。

概念図

区間加算 = 階段関数の重ね合わせ l r+1 l 高さ x の区間 [l,r] B1: 傾きの変化点（+x を l で、-x を r+1 で記録） B2: 切片補正（x*(l-1) を l で、-x*r を r+1 で記録） S(i) = i・B1.prefix(i) − B2.prefix(i)

ヒント（段階的開示）

ヒント1: 方向性
遅延伝播セグメント木を使えば区間加算・区間和は当然解けるが、通常の（1点更新・区間和用の）Binary Indexed Tree を2本組み合わせるだけでも同じことが定数倍軽く実現できないか考えよ。
ヒント2: アプローチ
区間 $[l,r]$ への加算を「位置 $l$ から先すべてに $x$ を足し、位置 $r+1$ から先すべてで打ち消す」という階段関数の重ね合わせとして捉える。位置 $i$ までの総和は $$S(i) = i \cdot B_1.\text{prefix}(i) - B_2.\text{prefix}(i)$$ という閉じた式で表せる。
ヒント3: 誘導（コード骨格） 
def range_add(l, r, x):
    B1.add(l, x);      B1.add(r + 1, -x)
    B2.add(l, x * (l - 1)); B2.add(r + 1, -x * r)

def prefix_sum(i):
    return B1.prefix(i) * i - B2.prefix(i)

模範解答 (Python)

import sys


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 prefix(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1

    b1 = BIT(n + 1)
    b2 = BIT(n + 1)

    def range_add(l, r, x):
        b1.add(l, x)
        b1.add(r + 1, -x)
        b2.add(l, x * (l - 1))
        b2.add(r + 1, -x * r)

    def prefix_sum(i):
        if i <= 0:
            return 0
        return b1.prefix(i) * i - b2.prefix(i)

    out = []
    for _ in range(q):
        t = int(data[idx]); idx += 1
        if t == 1:
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            x = int(data[idx]); idx += 1
            range_add(l, r, x)
        else:
            l = int(data[idx]); idx += 1
            r = int(data[idx]); idx += 1
            out.append(str(prefix_sum(r) - prefix_sum(l - 1)))

    print('\n'.join(out))


solve()
計算量: 各クエリ $O(\log N)$、全体 $O((N+Q)\log N)$。定数倍が軽く遅延伝播セグメント木より高速な場合が多い。

Step-by-Step 解説

1差分配列としての区間加算
区間加算を「階段関数」の重ね合わせとして表現し、傾きの変化点を $B_1$ に記録する。
2前置和の式を導出
$S(i) = i\cdot B_1.\text{prefix}(i) - \sum(x\cdot(p-1))$ の形になり、この補正項を $B_2$ で管理する。
3区間加算の実装
range_add(l,r,x) で $B_1,B_2$ にそれぞれ対応する値を記録する。
4区間和クエリ
prefix_sum を2箇所で評価し引き算するだけで任意区間の和が求まる。

よくあるミス

ミス原因正しい書き方
B2への加算値の符号・係数を間違える切片補正の式を正しく導出していないB2.add(l,x*(l-1))、B2.add(r+1,-x*r) を正確に対応させる
prefix_sum(0)呼び出しで範囲外エラー境界処理を怠るi<=0のときは0を即座に返す
r+1がNを超え配列外アクセスBITサイズをNちょうどにするBITサイズをN+1以上確保する
BIT1本だけで区間和も求めようとして詰まる1本では「傾き」しか表現できないことに気づかない区間加算・区間和の両方が必要ならBITを2本使う

次のステップ

  • 発展: 2次元に拡張した「矩形加算・矩形和クエリ」（BIT4本）
  • 発展: 区間加算・区間最大値クエリには使えないため、遅延伝播セグメント木との使い分けを整理する
  • 次回予告: Suffix Automaton拡張（複数文字列連結・全文字列共通部分文字列数え上げ）

自己評価

自分の回答

気づき・メモ