Range queries: Fenwick and segment trees

"Sum of positions 3..90" is easy once. It gets interesting when the data keeps changing between questions: scores updated, stock levels adjusted, intervals painted. This skill covers the three structures that answer range questions on changing data in O(log n): the Fenwick tree, the segment tree, and the segment tree with lazy propagation.

All ranges here are half-open [l, r) and positions are 0-based, exactly like iterators.

1. Static data: prefix sums

If the data never changes, precompute prefix[i] = sum of the first i values. Any range sum is then one subtraction:

#include <cstddef>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{5, 1, 4, 2, 3};
    std::vector<long> prefix(v.size() + 1, 0);
    for (std::size_t i = 0; i < v.size(); ++i) prefix[i + 1] = prefix[i] + v[i];
    // sum of [1, 4) = 1 + 4 + 2
    std::println("{}", prefix[4] - prefix[1]);
}

O(1) per query — but a single v[i] += d invalidates O(n) prefix entries. With q updates and q queries that's O(n·q). We want O(log n) for both.

2. The Fenwick tree

A Fenwick (binary indexed) tree is an array tree[1..n] where each cell holds the sum of a block of positions ending at its own index. The block length is lowbit(i) = i & -i, the lowest set bit of i:

i & -i works on unsigned integers because unary minus is defined modulo 2ᴺ: -i flips every bit above the lowest set one.

• prefix(i) — the sum of the first i positions — adds tree[i], strips the lowest bit (i -= i & -i) and repeats until i is 0. Each step clears a bit, so it takes at most log₂ n + 1 steps.
• add(i, d) must update every block containing position i: those are i, i + lowbit(i), … — walking up by adding the lowest bit.

The tree is 1-based for a reason: 0 & -0 == 0, so a walk from index 0 never moves. With 0-based input, shift by one inside add.

#include <cstddef>
#include <print>
#include <span>
#include <vector>

class Fenwick {
public:
    explicit Fenwick(std::size_t n) : tree_(n + 1, 0) {}
    void add(std::size_t i, long d) {                 // i is 0-based
        for (++i; i < tree_.size(); i += i & -i) tree_[i] += d;
    }
    long prefix(std::size_t i) const {                // sum of [0, i)
        long s = 0;
        for (; i > 0; i -= i & -i) s += tree_[i];
        return s;
    }
    long range(std::size_t l, std::size_t r) const { return prefix(r) - prefix(l); }

private:
    std::vector<long> tree_;
};

int main() {
    std::vector<int> v{5, 1, 4, 2, 3};
    Fenwick f(v.size());
    for (std::size_t i = 0; i < v.size(); ++i) f.add(i, v[i]);
    std::println("{} {}", f.range(1, 4), f.prefix(5));
    f.add(2, 10);
    std::println("{} {}", f.range(1, 4), f.prefix(5));
}

Building in O(n). n calls to add cost O(n log n). Instead, put each value in its own cell and push every cell once into its parent i + lowbit(i) — parents have larger indices, so each cell is complete before it is pushed:

for (std::size_t i = 1; i <= n; ++i) {
    tree[i] += values[i - 1];
    std::size_t parent = i + (i & -i);
    if (parent <= n) tree[parent] += tree[i];
}

Limits. range = prefix(r) − prefix(l) needs subtraction. That's fine for sums and xor (groups), but there's no way to "subtract" a minimum or a gcd. For those, use a segment tree.

3. Segment trees, bottom-up

A segment tree is a complete binary tree over the positions where every node stores the combination of its two children. The neat iterative layout uses an array of 2n slots: leaves at t[n + i], node k combines t[2k] and t[2k + 1], and the root is t[1]. It works for any n, not just powers of two.

• set(i, v): overwrite leaf n + i, then walk to the root recomputing each parent: O(log n).
• query(l, r): move both ends up the tree. Whenever l is a right child it can't share a parent with anything inside the range, so it contributes t[l++]; symmetrically, when r is odd, t[--r] contributes. Both ends climb one level per iteration: O(log n).

Which combinations? Anything that is a monoid: an associative operation with an identity element. In C++ that's a natural concept:

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <limits>
#include <print>
#include <span>
#include <vector>

template <class M>
concept Monoid = requires(const typename M::value_type& a, const typename M::value_type& b) {
    { M::identity() } -> std::convertible_to<typename M::value_type>;
    { M::combine(a, b) } -> std::convertible_to<typename M::value_type>;
};

struct MinInt {
    using value_type = int;
    static int identity() { return std::numeric_limits<int>::max(); }
    static int combine(int a, int b) { return std::min(a, b); }
};

template <Monoid M>
class SegTree {
public:
    using T = typename M::value_type;
    explicit SegTree(std::span<const T> v) : n_(v.size()), t_(2 * v.size(), M::identity()) {
        std::ranges::copy(v, t_.begin() + static_cast<std::ptrdiff_t>(n_));
        for (std::size_t i = n_; i-- > 1;) t_[i] = M::combine(t_[2 * i], t_[2 * i + 1]);
    }
    void set(std::size_t i, T v) {
        i += n_;
        t_[i] = v;
        for (i /= 2; i >= 1; i /= 2) t_[i] = M::combine(t_[2 * i], t_[2 * i + 1]);
    }
    T query(std::size_t l, std::size_t r) const {
        T left = M::identity(), right = M::identity();
        for (l += n_, r += n_; l < r; l /= 2, r /= 2) {
            if (l & 1) left = M::combine(left, t_[l++]);
            if (r & 1) right = M::combine(t_[--r], right);
        }
        return M::combine(left, right);
    }

private:
    std::size_t n_;
    std::vector<T> t_;
};

int main() {
    std::vector<int> v{4, -2, 7, 1, 9, 3};
    SegTree<MinInt> s{std::span<const int>(v)};
    std::println("{} {}", s.query(0, 6), s.query(2, 6));
    s.set(3, -5);
    std::println("{}", s.query(2, 6));
}

Order matters. Notice the two accumulators. Pieces found at the left end are appended to left; pieces at the right end are prepended to right (the right end moves leftwards). For sums or min the order is irrelevant, but for string concatenation or composing functions it isn't, and a single accumulator scrambles the result. Writing it this way costs nothing and makes the tree correct for every monoid.

Identity. query(l, l) returns identity(), and both accumulators start there, so it must be truly neutral: numeric_limits<T>::max() for min, lowest() for max, 0 for sum and gcd, "" for concatenation.

4. Lazy propagation: range updates

"Add 10 to every position in [l, r)" touches r − l leaves — O(n) per update if done leaf by leaf. Lazy propagation fixes this with a recursive tree in which each node [lo, hi) stores its sum and a pending tag:

• If an update covers a node completely, apply it to that node only: sum += delta · (hi − lo), lazy += delta. Don't touch the children.
• Before an update or query descends below a node, push its tag: apply it to both children and clear it. Afterwards, recompute the node's sum from its children.

Any range splits into O(log n) fully covered nodes plus two boundary paths, so both operations are O(log n). The one rule that must never break: a child's values are only correct after its parent's tag has been pushed. Forget a push in one place and some queries silently read stale sums.

void push(std::size_t node, std::size_t lo, std::size_t mid, std::size_t hi) {
    if (lazy_[node] != 0) {
        apply(2 * node, lo, mid, lazy_[node]);
        apply(2 * node + 1, mid, hi, lazy_[node]);
        lazy_[node] = 0;
    }
}

A recursive tree over [0, n) needs at most 4n nodes (root at index 1, children 2k and 2k + 1), and its recursion is only O(log n) deep.

5. Worked example: counting inversions with a Fenwick tree

An inversion is a pair i < j with v[i] > v[j]. Walk left to right and keep a Fenwick tree of the values seen so far: the inversions ending at j are the seen values greater than v[j], i.e. seen − prefix(v[j] + 1).

#include <cstddef>
#include <cstdint>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};   // values in [0, 10)
    std::vector<std::int64_t> tree(10 + 1, 0);    // Fenwick over values
    auto add = [&](std::size_t i) { for (++i; i < tree.size(); i += i & -i) ++tree[i]; };
    auto prefix = [&](std::size_t i) { std::int64_t s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; };

    std::int64_t inversions = 0, seen = 0;
    for (int x : v) {
        inversions += seen - prefix(static_cast<std::size_t>(x) + 1);   // seen values > x
        add(static_cast<std::size_t>(x));
        ++seen;
    }
    std::println("{}", inversions);
}

O(n log V) instead of the O(n²) double loop. The same "Fenwick over values" idea answers rank queries ("how many values ≤ x so far?").

Faded example — your turn

Range add with point queries, using a Fenwick tree of differences: adding d to [l, r) changes the difference array at just two places. Fill in the two lines, then answer: what is value_at(i) in terms of prefix?

void range_add(std::size_t l, std::size_t r, long d) {
    f.add(l, /* ??? */);
    if (r < n) f.add(r, /* ??? */);
}
long value_at(std::size_t i) { return /* ??? */; }

6. Choosing

7. Overflow

Range sums grow quickly: a thousand values of 4·10⁹ already exceed 32 bits. Use std::int64_t for sums and lazy tags, and compute delta · length in 64 bits. Signed overflow is undefined behaviour, and UBSan will report it.

Summary

• Half-open, 0-based ranges outside; the Fenwick tree is 1-based inside.
• Fenwick: walk up by i += i & -i (add), down by i -= i & -i (prefix); ranges need an inverse, so sums and xor only.
• Iterative segment tree: leaves at n + i, two accumulators to keep monoid order, identity() for empty ranges.
• Lazy propagation: tag fully covered nodes, push before descending, recompute after.
• Everything is O(log n) per operation; use 64-bit sums.