Fenwick and segment trees¶
Prefix sums answer static ranges. When values change, store a hierarchy of aggregates and update only the nodes whose ranges contain the changed index.
Chooser¶
| Requirement | Prefer | Reason |
|---|---|---|
| Point add + prefix/range sum | Fenwick | Small, fast, O(n) memory |
| Point assignment + range aggregate | Segment tree | Direct associative merging |
| Range update + point query | Fenwick difference | Two boundary updates |
| Range update + range query | Lazy segment tree | Defers whole-range work |
| Static queries only | Prefix/sparse table | Less machinery |
Fenwick ownership¶
flowchart LR
accTitle: Fenwick tree movement by lowest set bit
accDescr: An update adds the lowest set bit to visit progressively larger owning ranges, while a prefix query removes the lowest set bit to collect disjoint ranges covering the prefix.
U["update index i+1"] -->|"+ lowbit"| P["next owning range"]
P -->|"+ lowbit"| Q["larger owning range"]
S["prefix end"] -->|"- lowbit"| T["remaining prefix"]
T -->|"- lowbit"| V["remaining prefix"]class FenwickTree:
"""Support point additions and prefix/range sums in logarithmic time."""
def __init__(self, size: int) -> None:
if size < 0:
raise ValueError("size must be nonnegative")
self.size = size
self.tree = [0] * (size + 1)
def add(self, index: int, delta: int) -> None:
if not 0 <= index < self.size:
raise IndexError("index outside Fenwick tree")
cursor = index + 1
while cursor <= self.size:
self.tree[cursor] += delta
# Add the lowest set bit to reach the next owning range.
cursor += cursor & -cursor
def prefix_sum(self, end: int) -> int:
"""Return the sum of the half-open prefix ``[0, end)``."""
if not 0 <= end <= self.size:
raise IndexError("prefix end outside Fenwick tree")
total = 0
cursor = end
while cursor:
total += self.tree[cursor]
# Remove the lowest set bit to visit the parent prefix.
cursor -= cursor & -cursor
return total
def range_sum(self, left: int, right: int) -> int:
if not 0 <= left <= right <= self.size:
raise IndexError("range outside Fenwick tree")
return self.prefix_sum(right) - self.prefix_sum(left)
class FenwickTree {
public:
explicit FenwickTree(int size) : size_(size) {
if (size < 0) {
throw std::invalid_argument("size must be nonnegative");
}
tree_.assign(static_cast<std::size_t>(size) + 1, 0);
}
void add(int index, long long delta) {
require_index(index);
for (int cursor = index + 1; cursor <= size_;
cursor += cursor & -cursor) {
// Each visited node owns a larger range containing index.
tree_[cursor] += delta;
}
}
long long prefix_sum(int end) const {
if (end < 0 || end > size_) {
throw std::out_of_range("prefix end outside Fenwick tree");
}
long long total = 0;
for (int cursor = end; cursor > 0; cursor -= cursor & -cursor) {
// Removing the lowest set bit visits the parent prefix.
total += tree_[cursor];
}
return total;
}
long long range_sum(int left, int right) const {
if (left < 0 || left > right || right > size_) {
throw std::out_of_range("range outside Fenwick tree");
}
return prefix_sum(right) - prefix_sum(left);
}
private:
void require_index(int index) const {
if (index < 0 || index >= size_) {
throw std::out_of_range("index outside Fenwick tree");
}
}
int size_;
std::vector<long long> tree_;
};
class FenwickTree {
public:
explicit FenwickTree(int size) : size_(size) {
if (size < 0) {
throw std::invalid_argument("size must be nonnegative");
}
tree_.assign(static_cast<std::size_t>(size) + 1, 0);
}
void add(int index, long long delta) {
require_index(index);
for (int cursor = index + 1; cursor <= size_;
cursor += cursor & -cursor) {
// Each visited node owns a larger range containing index.
tree_[cursor] += delta;
}
}
long long prefix_sum(int end) const {
if (end < 0 || end > size_) {
throw std::out_of_range("prefix end outside Fenwick tree");
}
long long total = 0;
for (int cursor = end; cursor > 0; cursor -= cursor & -cursor) {
// Removing the lowest set bit visits the parent prefix.
total += tree_[cursor];
}
return total;
}
long long range_sum(int left, int right) const {
if (left < 0 || left > right || right > size_) {
throw std::out_of_range("range outside Fenwick tree");
}
return prefix_sum(right) - prefix_sum(left);
}
private:
void require_index(int index) const {
if (index < 0 || index >= size_) {
throw std::out_of_range("index outside Fenwick tree");
}
}
int size_;
std::vector<long long> tree_;
};
Iterative segment tree¶
class SegmentTree:
"""Support point assignment and half-open range sums."""
def __init__(self, values: list[int]) -> None:
self.size = len(values)
self.tree = [0] * (2 * self.size)
self.tree[self.size :] = values
for node in range(self.size - 1, 0, -1):
# Each internal node owns the sum of its two children.
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def set(self, index: int, value: int) -> None:
if not 0 <= index < self.size:
raise IndexError("index outside segment tree")
node = index + self.size
self.tree[node] = value
while node > 1:
node //= 2
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def range_sum(self, left: int, right: int) -> int:
if not 0 <= left <= right <= self.size:
raise IndexError("range outside segment tree")
left += self.size
right += self.size
total = 0
while left < right:
if left & 1:
total += self.tree[left]
left += 1
if right & 1:
right -= 1
total += self.tree[right]
# Move from the selected boundary nodes to their parents.
left //= 2
right //= 2
return total
class SegmentTree {
public:
explicit SegmentTree(const std::vector<int>& values)
: size_(static_cast<int>(values.size())), tree_(2 * values.size(), 0) {
std::copy(values.begin(), values.end(), tree_.begin() + size_);
for (int node = size_ - 1; node > 0; --node) {
// Each internal node owns the sum of its two children.
tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
}
}
void set(int index, long long value) {
if (index < 0 || index >= size_) {
throw std::out_of_range("index outside segment tree");
}
int node = index + size_;
tree_[node] = value;
while (node > 1) {
node /= 2;
tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
}
}
long long range_sum(int left, int right) const {
if (left < 0 || left > right || right > size_) {
throw std::out_of_range("range outside segment tree");
}
left += size_;
right += size_;
long long total = 0;
while (left < right) {
if (left % 2 == 1) {
total += tree_[left++];
}
if (right % 2 == 1) {
total += tree_[--right];
}
// Move from the selected boundary nodes to their parents.
left /= 2;
right /= 2;
}
return total;
}
private:
int size_;
std::vector<long long> tree_;
};
class SegmentTree {
public:
explicit SegmentTree(const std::vector<int>& values)
: size_(static_cast<int>(values.size())), tree_(2 * values.size(), 0) {
std::copy(values.begin(), values.end(), tree_.begin() + size_);
for (int node = size_ - 1; node > 0; --node) {
// Each internal node owns the sum of its two children.
tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
}
}
void set(int index, long long value) {
if (index < 0 || index >= size_) {
throw std::out_of_range("index outside segment tree");
}
int node = index + size_;
tree_[node] = value;
while (node > 1) {
node /= 2;
tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
}
}
long long range_sum(int left, int right) const {
if (left < 0 || left > right || right > size_) {
throw std::out_of_range("range outside segment tree");
}
left += size_;
right += size_;
long long total = 0;
while (left < right) {
if (left % 2 == 1) {
total += tree_[left++];
}
if (right % 2 == 1) {
total += tree_[--right];
}
// Move from the selected boundary nodes to their parents.
left /= 2;
right /= 2;
}
return total;
}
private:
int size_;
std::vector<long long> tree_;
};
Both operations are O(log n). The examples use half-open [left, right)
ranges; mixing inclusive and exclusive boundaries is the most common defect.