Range queries and coordinate state.

Prefix sums solve static range sums because subtraction removes the unwanted prefix. Updates break that table. Fenwick and segment trees retain partial aggregates so an update changes logarithmically many nodes and a query combines logarithmically many disjoint blocks.

Choose by query shape and update shape

Fenwick is the smallest and usually fastest choice for an invertible prefix aggregate such as addition. A segment tree is necessary when an arbitrary range cannot be obtained from two prefixes: maximum has no inverse operation analogous to subtraction.

Coordinate compression

Copy every value that may be inserted or queried, sort, erase duplicates, then replace each value with its rank. Compression preserves comparisons. It does not preserve numeric distances. If a query uses transformed values such as 2*x, include those values in the compression domain or use lower/upper bounds directly against the sorted original values.

coordinate_compression.cppstd::vector<int> coordinates(values.begin(), values.end());
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(
    std::unique(coordinates.begin(), coordinates.end()),
    coordinates.end()
);

const std::size_t rank = static_cast<std::size_t>(
    std::lower_bound(coordinates.begin(), coordinates.end(), value) -
    coordinates.begin()
);

std::unique only moves adjacent duplicates to the tail and returns the new logical end. erase performs the actual shrink. lower_bound(x) gives the number of distinct values strictly less than x. upper_bound(x) gives the number less than or equal to x.

Fenwick tree

A Fenwick tree is internally one-indexed. Node tree[i] stores the sum of a block of length lowbit(i) ending at i, where lowbit(i) isolates the least significant set bit. Update moves to the next block containing the index. Prefix query removes the final block.

fenwick.cppclass Fenwick {
public:
    explicit Fenwick(std::size_t size) : tree_(size + 1, 0) {}

    void add(std::size_t index, std::int64_t delta) {
        for (++index; index < tree_.size();
             index += index & (~index + 1))
            tree_[index] += delta;
    }

    std::int64_t prefix(std::size_t end) const {
        std::int64_t sum = 0;
        for (; end > 0; end -= end & (~end + 1))
            sum += tree_[end];
        return sum;
    }

    std::int64_t range(std::size_t begin, std::size_t end) const {
        return prefix(end) - prefix(begin);
    }

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

~i + 1 is unsigned two’s-complement negation, so i & (~i + 1) is the low bit without mixing signed and unsigned types. Index zero cannot be used internally because its low bit is zero and an update loop would never advance.

A difference array stored in a Fenwick supports range-add and point query: add value at l and -value at r+1, then query the prefix at i. Range-add plus range-sum requires two Fenwick trees holding the coefficient and constant of the resulting prefix function.

Fenwick binary lifting and order statistics

If Fenwick values are nonnegative frequencies, prefix sums are monotone. Descend powers of two from largest to smallest to find the first index whose cumulative frequency reaches a target. This reuses the internal partial sums directly and costs O(log n), while an outer binary search calling prefix would cost O(log² n).

fenwick_lower_bound.cppstd::size_t lower_bound(std::int64_t target) const {
    std::size_t position = 0;
    const std::size_t size = tree_.size() - 1;

    for (std::size_t step = std::bit_floor(size);
         step > 0;
         step >>= 1) {
        const std::size_t next = position + step;
        if (next <= size && tree_[next] < target) {
            position = next;
            target -= tree_[next];
        }
    }
    return position; // 0-based first index reaching the original target
}

With coordinate-compressed values and counts, this is a dynamic multiset supporting insert, erase, count below x, and k-th smallest in logarithmic time. Sliding medians with deletions are a direct use when the value domain can be known in advance.

Sweep plus Fenwick counting

“Count values smaller to the right” has two constraints: j > i and value[j] < value[i]. Sweep right to left so every inserted value already satisfies the index constraint. The Fenwick tree handles the value constraint.

count_smaller_after.cppstd::vector<int> count_smaller_after(
    std::span<const int> values
) {
    std::vector<int> sorted(values.begin(), values.end());
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());

    Fenwick counts(sorted.size());
    std::vector<int> answer(values.size());
    for (std::size_t offset = values.size(); offset > 0; --offset) {
        const std::size_t index = offset - 1;
        const auto rank = static_cast<std::size_t>(
            std::lower_bound(sorted.begin(), sorted.end(), values[index]) -
            sorted.begin()
        );
        answer[index] = static_cast<int>(counts.prefix(rank));
        counts.add(rank, 1);
    }
    return answer;
}

Inversion Count uses the same sweep or a merge-sort cross-count. Reverse Pairs counts earlier values greater than 2*x. Widen before doubling. Count of Range Sum applies the same reasoning to prefix sums: for each current prefix p, count earlier prefixes in [p - upper, p - lower].

Iterative segment tree

Store leaves in tree[n..2n) and parents before them. A query maintains two accumulators while l and r move upward. If l is a right child, consume it and advance. If r is a right boundary, retreat and consume its left sibling.

sum_segment_tree.cppclass SumSegmentTree {
public:
    explicit SumSegmentTree(std::span<const std::int64_t> values)
        : size_(values.size()), tree_(2 * values.size(), 0) {
        std::copy(values.begin(), values.end(), tree_.begin() + size_);
        for (std::size_t node = size_; node-- > 1;)
            tree_[node] = tree_[2 * node] + tree_[2 * node + 1];
    }

    void set(std::size_t index, std::int64_t value) {
        index += size_;
        tree_[index] = value;
        while (index > 1) {
            index >>= 1;
            tree_[index] = tree_[2 * index] + tree_[2 * index + 1];
        }
    }

    std::int64_t query(std::size_t begin, std::size_t end) const {
        std::int64_t left_sum = 0, right_sum = 0;
        for (begin += size_, end += size_; begin < end;
             begin >>= 1, end >>= 1) {
            if (begin & 1U) left_sum += tree_[begin++];
            if (end & 1U) right_sum = tree_[--end] + right_sum;
        }
        return left_sum + right_sum;
    }

private:
    std::size_t size_;
    std::vector<std::int64_t> tree_;
};

For a noncommutative merge such as matrix multiplication or string concatenation, the separate left and right accumulators are mandatory: append consumed left nodes to left_result, prepend consumed right nodes to right_result, then merge the two.

Lazy propagation

A lazy tag records an update that already affects the current aggregate but has not yet been pushed to children. Range addition composes by addition. Range assignment does not compose with addition the same way. a combined tree must explicitly define whether assignment clears an earlier addition and how a later addition modifies an assignment tag.

lazy_range_sum_core.cppvoid apply(
    std::size_t node,
    std::size_t left,
    std::size_t right,
    std::int64_t value
) {
    tree_[node] += value * static_cast<std::int64_t>(right - left);
    lazy_[node] += value;
}

void push(std::size_t node, std::size_t left, std::size_t right) {
    if (lazy_[node] == 0 || right - left == 1) return;
    const std::size_t middle = left + (right - left) / 2;
    apply(2 * node, left, middle, lazy_[node]);
    apply(2 * node + 1, middle, right, lazy_[node]);
    lazy_[node] = 0;
}

A recursive segment tree commonly allocates 4*n entries so a non-power-of-two input has room for the complete recursive layout. Iterative lazy trees are possible but substantially easier to get wrong.

Segment trees as DP transition accelerators

Ordinary LIS asks for the best earlier state at any smaller value. Tails plus binary search exploits special structure. If consecutive values must also differ by at most k, the transition becomes a maximum over the value interval [x-k, x). Coordinate-compress the values and store the best DP length at each rank in a max segment tree.

bounded_lis_transition.cppfor (const int value : values) {
    const std::size_t left = rank_of_first_at_least(value - limit);
    const std::size_t right = rank_of_first_at_least(value);
    const int current = 1 + segment.query(left, right);
    segment.update_max(right, current);
    answer = std::max(answer, current);
}

The sweep order enforces the index condition: only earlier positions have entered the tree. Sorting by one key and querying a tree over another turns many two-dimensional dominance problems into a one- dimensional range query. Equal-key batches may need delayed updates so items in the same batch cannot use each other.

Sparse table

Level k stores answers for every block of length 2^k. Any query is covered by two blocks of the largest fitting power of two: one beginning at l and one ending at r. They may overlap. That is valid for min, max, and gcd, but invalid for sum.

sparse_minimum_query.cppint query(std::size_t begin, std::size_t end) const { // [begin, end)
    const std::size_t length = end - begin;
    const std::size_t level =
        static_cast<std::size_t>(logarithm_[length]);
    const std::size_t block = std::size_t{1} << level;
    return std::min(
        table_[level][begin],
        table_[level][end - block]
    );
}

Build time and memory are O(n log n). Query time is constant. A disjoint sparse table extends constant-time static queries to any associative operation by precomputing nonoverlapping prefix and suffix blocks, but the ordinary form covers the common idempotent case.