問題
座標値が最大 $10^{18}$ に達する1次元空間上での点更新・区間和クエリを処理せよ。
- クエリ型 1:
1 x v— 座標 $x$ の値を $v$ に加算する（初期値 0） - クエリ型 2:
2 l r— 座標区間 $[l, r]$ の値の総和を出力する
制約
| パラメータ | 範囲 |
|---|---|
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
| $x, l, r$ | $1 \le x, l, r \le 10^{18}$ |
| $v$ | $-10^9 \le v \le 10^9$ |
| 答え | 64 bit 整数に収まる |
入出力例
入力例 1
6
1 1000000000 5
1 999999999 3
2 999999999 1000000001
1 500000000000000000 100
2 1 1000000000000000000
1 999999999 7出力例 1
8
108区間[999999999,1000000001]の和=3+5=8。全区間の和=3+5+100=108（7は後で加算）。
概念図: 動的セグメント木のノード生成
ヒント（段階的開示）
ヒント1: 方向性
座標が $10^{18}$ に達するため配列で管理できない。「動的セグメント木」は実際にアクセスされたノードのみを生成するポインタベースのセグメント木で、$Q$ 回の操作で最大 $O(Q \log V)$ ノードしか生成されない。
ヒント2: アプローチ
- 各ノード:
val, left, right（子は初期値 None） update(node, lo, hi, x, v): ノードの値を更新し、子が None なら Node() を生成してから再帰query(node, lo, hi, ql, qr): node が None なら 0 を返す- 深さは最大 $\log_2(10^{18}) \approx 60$
ヒント3: コード骨格
class Node:
__slots__ = ['val', 'left', 'right']
def __init__(self):
self.val = 0
self.left = self.right = None
def update(node, lo, hi, x, v):
node.val += v
if lo == hi: return
mid = (lo + hi) >> 1
if x <= mid:
if node.left is None: node.left = Node()
update(node.left, lo, mid, x, v)
else:
if node.right is None: node.right = Node()
update(node.right, mid+1, hi, x, v)
def query(node, lo, hi, ql, qr):
if node is None: return 0 # 未生成 → 値は 0
if ql <= lo and hi <= qr: return node.val
mid = (lo + hi) >> 1
res = 0
if ql <= mid: res += query(node.left, lo, mid, ql, qr)
if qr > mid: res += query(node.right, mid+1, hi, ql, qr)
return res模範解答 (Python)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)
class Node:
__slots__ = ['val', 'left', 'right']
def __init__(self):
self.val = 0
self.left = self.right = None
L_BOUND = 1
R_BOUND = 10**18
def update(node, lo, hi, x, v):
"""座標 x に v を加算"""
node.val += v
if lo == hi:
return
mid = (lo + hi) >> 1
if x <= mid:
if node.left is None:
node.left = Node()
update(node.left, lo, mid, x, v)
else:
if node.right is None:
node.right = Node()
update(node.right, mid + 1, hi, x, v)
def query(node, lo, hi, ql, qr):
"""区間 [ql, qr] の総和を返す"""
if node is None:
return 0
if ql <= lo and hi <= qr:
return node.val
mid = (lo + hi) >> 1
res = 0
if ql <= mid:
res += query(node.left, lo, mid, ql, qr)
if qr > mid:
res += query(node.right, mid + 1, hi, ql, qr)
return res
def main():
Q = int(input())
root = Node()
out = []
for _ in range(Q):
line = list(map(int, input().split()))
if line[0] == 1:
_, x, v = line
update(root, L_BOUND, R_BOUND, x, v)
else:
_, l, r = line
out.append(str(query(root, L_BOUND, R_BOUND, l, r)))
print('\n'.join(out))
main()Step-by-Step 解説
Step 1: 動的セグメント木の着想
通常のセグメント木は $O(N)$ のノードを事前確保するが、$N = 10^{18}$ では不可能。動的版は「初めてアクセスされたときにノードを生成」する遅延初期化で解決する。
Step 2: ノード生成のタイミング
update 関数が各レベルで子へ進む際、子が None なら Node() を生成。$Q$ 回の update で最大 $Q \times \log_2(10^{18}) \approx Q \times 60$ ノードが生成される。
Step 3: query の NULL チェック
子ノードが None の場合は「その部分木は全て 0」なので 0 を返す。これにより未初期化ノードへのアクセスを安全に処理できる。update では必ず Node を生成してから再帰するが、query では生成不要。
Step 4: 計算量の整理
| 指標 | 値 |
|---|---|
| 空間 | $O(Q \log V)$ ノード（$V = 10^{18}$, $\log V \approx 60$） |
| 1クエリの時間 | $O(\log V)$ |
| 全体時間 | $O(Q \log V)$ |
| 最大再帰深度 | $\approx 60$ |
Step 5: 遅延伝播との統合
動的セグメント木に遅延伝播（Lazy Propagation）を加えることで区間更新も $O(\log V)$ で処理できる。その場合は push_down 時に子が None なら生成してから伝播する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| query で None チェック忘れ | 未生成ノードへのアクセス | if node is None: return 0 |
| query でノード生成してしまう | 無用なノードが増える | query では生成不要、None なら 0 返却 |
| setrecursionlimit 不足 | 深さ60×Qで超過 | sys.setrecursionlimit(300000) |
| mid の右子の lo を間違える | 右子を mid+1 ではなく mid から始める | update(node.right, mid+1, hi, ...) |
次のステップ
発展問題: 動的セグメント木 + 遅延伝播（Lazy Dynamic Segment Tree）で区間加算 + 区間最大値クエリ。永続動的セグメント木（バージョン管理）への拡張。