リリース・改善中
セグメント木 ガイド · 3/6
この章は現在、英語でのみ提供しています。
This chapter builds the iterative (bottom-up) segment tree in Python, explains each line, ports it to C++, Java, and TypeScript, and adds a Fenwick tree for sums. Ranges are half-open: [left, right).
class SegmentTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * self.n + list(values)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
total = 0
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
total += self.tree[lo]
lo += 1
if hi & 1:
hi -= 1
total += self.tree[hi]
lo //= 2
hi //= 2
return total
st = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
print(st.query(2, 6)) # 26
st.update(3, 0)
print(st.query(2, 6)) # 17Line by line:
self.tree = [0] * self.n + list(values): a 2n array whose second half tree[n..2n) holds the elements. Index 0 is unused.n-1 down to 1, combining children 2i and 2i+1, which are always ready first: O(n).update: overwrite leaf index + n, then climb with i //= 2, recomputing each parent: O(log n).lo, hi: the query bounds as leaf positions.lo & 1: an odd lo is a right child whose parent reaches outside the range, so take this node and step right.hi & 1: if the exclusive end is odd, node hi - 1 is inside the range, so take it.lo //= 2, hi //= 2: climb a level until the ends meet.For a minimum tree, replace + with min and the initial 0 with float("inf"). For order-sensitive operations, gather the left and right sides separately and combine them in order at the end.
Sums overflow int easily; use long long.
#include <vector>
struct SegmentTree {
int n;
std::vector<long long> tree;
explicit SegmentTree(const std::vector<long long>& values)
: n(static_cast<int>(values.size())), tree(2 * values.size()) {
for (int i = 0; i < n; ++i) tree[n + i] = values[i];
for (int i = n - 1; i > 0; --i) tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void update(int index, long long value) {
int i = index + n;
tree[i] = value;
while (i > 1) { i /= 2; tree[i] = tree[2 * i] + tree[2 * i + 1]; }
}
long long query(int left, int right) const { // [left, right)
long long total = 0;
for (int lo = left + n, hi = right + n; lo < hi; lo /= 2, hi /= 2) {
if (lo & 1) total += tree[lo++];
if (hi & 1) total += tree[--hi];
}
return total;
}
};public final class SegmentTree {
private final int n;
private final long[] tree;
public SegmentTree(long[] values) {
n = values.length;
tree = new long[2 * n];
System.arraycopy(values, 0, tree, n, n);
for (int i = n - 1; i > 0; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];
}
public void update(int index, long value) {
int i = index + n;
tree[i] = value;
while (i > 1) { i /= 2; tree[i] = tree[2 * i] + tree[2 * i + 1]; }
}
public long query(int left, int right) { // [left, right)
long total = 0;
for (int lo = left + n, hi = right + n; lo < hi; lo /= 2, hi /= 2) {
if ((lo & 1) == 1) total += tree[lo++];
if ((hi & 1) == 1) total += tree[--hi];
}
return total;
}
}class SegmentTree {
private readonly n: number;
private readonly tree: number[];
constructor(values: number[]) {
this.n = values.length;
this.tree = new Array<number>(this.n).fill(0).concat(values);
for (let i = this.n - 1; i > 0; i--) this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
}
update(index: number, value: number): void {
let i = index + this.n;
this.tree[i] = value;
while (i > 1) { i >>= 1; this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1]; }
}
query(left: number, right: number): number {
let total = 0;
for (let lo = left + this.n, hi = right + this.n; lo < hi; lo >>= 1, hi >>= 1) {
if (lo & 1) total += this.tree[lo++];
if (hi & 1) total += this.tree[--hi];
}
return total;
}
}A Fenwick tree (BIT) stores prefix sums in chunks and moves by i & -i, the lowest set bit of i. It must be 1-indexed.
class FenwickTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1) # tree[0] is unused
def add(self, index, delta): # a[index] += delta
i = index + 1
while i <= self.n:
self.tree[i] += delta
i += i & -i
def prefix_sum(self, count): # a[0] + ... + a[count-1]
total = 0
while count > 0:
total += self.tree[count]
count -= count & -count
return total
def range_sum(self, left, right): # [left, right)
return self.prefix_sum(right) - self.prefix_sum(left)
bit = FenwickTree(8)
for i, v in enumerate([5, 3, 7, 9, 6, 4, 1, 2]):
bit.add(i, v)
print(bit.range_sum(2, 6)) # 26
bit.add(3, -9) # same as setting a[3] = 0
print(bit.range_sum(2, 6)) # 17It only accepts additions, so overwriting means adding new - old. Range sums rely on subtraction, so non-invertible operations such as minimum do not fit.
The iterative segment tree is a 2n array plus three short loops, and it looks the same in every language. For sums a Fenwick tree is enough; for minimums, maximums, and other non-invertible operations, use the segment tree.
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。