Day 008-Q4 | 平方分割

問題

長さ $N$ の数列に対して、以下の2種類のクエリを $Q$ 回処理せよ。

1 l r x: $A_l, \ldots, A_r$ に $x$ を加算
2 l r: $A_l + \ldots + A_r$ を出力

制約

$1 \le N, Q \le 10^5$

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

$-10^9 \le A_i \le 10^9$

$-10^9 \le x \le 10^9$

入出力例

入力例 1

出力例 1

45
42

ヒント (段階的開示)

ヒント1: 方向性

平方分割（ブロック分解）。配列をサイズ $\sqrt{N}$ のブロックに分けて管理。

ヒント2: アプローチ

各ブロックに「ブロック全体への加算量（lazy）」を保持。クエリが境界をまたぐ場合、端は直接更新し、完全に含まれるブロックは lazy で遅延管理。

ヒント3: 誘導

B = int(N ** 0.5) + 1
lazy = [0] * (N // B + 1)

模範解答 (Python)

import sys
input = sys.stdin.readline

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

    B = int(N ** 0.5) + 1
    num_blocks = (N + B - 1) // B
    lazy = [0] * num_blocks

    def block(i):
        return i // B

    def block_start(b):
        return b * B

    def block_end(b):
        return min((b + 1) * B - 1, N - 1)

    def range_add(l, r, x):
        l -= 1; r -= 1
        bl, br = block(l), block(r)
        if bl == br:
            for i in range(l, r + 1):
                A[i] += x
        else:
            for i in range(l, block_end(bl) + 1):
                A[i] += x
            for b in range(bl + 1, br):
                lazy[b] += x
            for i in range(block_start(br), r + 1):
                A[i] += x

    def range_sum(l, r):
        l -= 1; r -= 1
        bl, br = block(l), block(r)
        total = 0
        if bl == br:
            total = sum(A[l:r+1]) + lazy[bl] * (r - l + 1)
        else:
            le = block_end(bl)
            total += sum(A[l:le+1]) + lazy[bl] * (le - l + 1)
            for b in range(bl + 1, br):
                bs, be = block_start(b), block_end(b)
                total += sum(A[bs:be+1]) + lazy[b] * (be - bs + 1)
            rs = block_start(br)
            total += sum(A[rs:r+1]) + lazy[br] * (r - rs + 1)
        return total

    out = []
    for _ in range(Q):
        q = list(map(int, input().split()))
        if q[0] == 1:
            range_add(q[1], q[2], q[3])
        else:
            out.append(range_sum(q[1], q[2]))

    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1ブロック分割
サイズ $B = \sqrt{N}$ のブロックに分割し、各ブロックに lazy を持つ。

2区間加算
端数ブロックは要素ごと更新、完全ブロックは lazy のみで $O(1)$。

3区間合計
端数ブロックは sum + lazy * 要素数、完全ブロックは sum + lazy * B。

4計算量
各クエリ $O(\sqrt{N})$ → 全体 $O(Q\sqrt{N})$。

よくあるミス

ミス	原因	正しい書き方
合計時に lazy を掛ける要素数を誤る	端数でブロック全体の要素数を使う	実際の要素数 `(le - l + 1)` で計算
ブロック境界の計算ミス	0-indexed / 1-indexed の混在	最初に 0-indexed に変換

次のステップ

発展問題: 区間更新・区間最小値クエリ（Mo's algorithm / 遅延セグメント木と比較）

自己評価

完全理解おおむね理解要復習

Day 008-Q4 — 平方分割

問題

制約