Algorithms - Segment Tree and Fenwick Tree - efficient range queries and updates

Published Mar 14, 2026

Posted in
question
.net
c#
programming

Intro

At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

Efficient prefix and pattern matching - solved by Trie and KMP String Search
Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

Today I am going to talk about data structures that help repeatedly query aggregates (sum, min, max, etc.) over ranges of an array and perform updates at the same time.

Segment Trees and Fenwick Trees (also called Binary Indexed Trees or BIT) both solve this in O(log n) per operation, turning impossible brute-force solutions into efficient ones.

When to use them

Use these when the problem has:

Frequent range queries (sum/min/max/count of elements in [L, R])
Frequent point updates (change value at index i)
Array size n ≈ 10⁵–10⁶ and query count q ≈ 10⁵–10⁶

Classic scenarios:

Mutable range sum queries
Range minimum queries with updates
Counting inversions or coordinate compression helpers
Dynamic frequency queries

A segment tree is more flexible (supports range updates via lazy propagation, any associative operation like gcd/max).

A Fenwick tree is simpler and lighter on memory, ideal for when you only need prefix sums (and derive range sums via prefix[R] - prefix[L-1]).

Segment Tree - Range sum query (mutable)

A Segment Tree is a full binary tree where:

Each node represents a range (segment) of the array
Leaf nodes hold individual array elements
Internal nodes hold the aggregate (sum/min/max) of their children
Built in O(n) space (typically 4n array size) and O(n) time

Operations:

Build: O(n)
Update (point): O(log n)
Query (range): O(log n)

Classic problem: Range Sum Query - Mutable

Problem statement: Given an integer array nums, handle multiple queries of the following types:

Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive, where left <= right.

int[] nums = [1, 3, 5];
var st = new SegmentTree(nums);
Console.WriteLine(st.Query(0, 2)); // 9
st.Update(1, 2);
Console.WriteLine(st.Query(0, 2)); // 8

public class SegmentTree
{
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums)
    {
        n = nums.Length;
        tree = new int[4 * n];
        Build(1, 0, n - 1, nums);
    }

    private void Build(int node, int start, int end, int[] nums)
    {
        if (start == end)
        {
            tree[node] = nums[start];
            return;
        }
        var mid = start + (end - start) / 2;
        Build(2 * node, start, mid, nums);
        Build(2 * node + 1, mid + 1, end, nums);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public void Update(int index, int val)
    {
        UpdateHelper(1, 0, n - 1, index, val);
    }

    private void UpdateHelper(int node, int start, int end, int idx, int val)
    {
        if (start == end)
        {
            tree[node] = val;
            return;
        }
        var mid = start + (end - start) / 2;
        if (idx <= mid)
            UpdateHelper(2 * node, start, mid, idx, val);
        else
            UpdateHelper(2 * node + 1, mid + 1, end, idx, val);

        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    public int Query(int left, int right)
    {
        return QueryHelper(1, 0, n - 1, left, right);
    }

    private int QueryHelper(int node, int start, int end, int l, int r)
    {
        if (r < start || end < l) return 0;          // outside
        if (l <= start && end <= r) return tree[node]; // fully inside

        var mid = start + (end - start) / 2;
        var leftSum = QueryHelper(2 * node, start, mid, l, r);
        var rightSum = QueryHelper(2 * node + 1, mid + 1, end, l, r);
        return leftSum + rightSum;
    }
}

Complexity:

Build: O(n)
Update & Query: O(log n)
Space: O(4n) ≈ O(n)

Fenwick Tree - Range sum query

A Fenwick Tree is an array-based structure that uses bit manipulation to simulate tree-like prefix computations. It only needs O(n) space and is easier to code for sum-based problems.

Key operations:

update(idx, delta) - add delta to position idx
prefixSum(idx) - sum from 1 to idx
- Range sum [L,R] = prefix(R) - prefix(L-1)

Note: Fenwick Trees are 1-indexed in practice.

Here is the same usage as above, but using a Fenwick Tree:

int[] nums = [1, 3, 5];
var ft = new FenwickTree(nums);
Console.WriteLine(ft.Query(0, 2)); // 9
ft.Update(1, 2); //1-based
Console.WriteLine(ft.Query(0, 2)); // 8

public class FenwickTree
{
    private int[] bit;
    private int[] values; // store original values for set-style updates
    private int n;

    public FenwickTree(int[] nums)
    {
        n = nums.Length;
        values = new int[n];
        bit = new int[n + 2]; // 1-based + extra
        for (var i = 0; i < n; i++)
        {
            values[i] = nums[i];
            Add(i + 1, nums[i]);
        }
    }

    private void Add(int idx, int delta)
    {
        while (idx <= n)
        {
            bit[idx] += delta;
            idx += idx & -idx; // lowest set bit
        }
    }

    public void Update(int index, int val)
    {
        var delta = val - values[index]; // compute delta for set
        values[index] = val;
        Add(index + 1, delta);
    }

    private int PrefixSum(int idx)
    {
        var sum = 0;
        while (idx > 0)
        {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    }

    public int Query(int left, int right)
    {
        return PrefixSum(right + 1) - PrefixSum(left);
    }
}

Complexity:

Update & Prefix Query: O(log n)
Range Query: O(log n)
Space: O(n)

Comparison

Space:

Segment:O(4n)
Fenwick: O(n)

Build time:

Segment:O(n)
Fenwick: O(n log n)

Update

Segment:O(log n)
Fenwick: O(log n)

Range Query

Segment:O(log n)
Fenwick: O(log n) (via two prefixes)

Flexibility

Segment:"High: min/max/sum/gcd, lazy range updates"
Fenwick: Mostly sums (or invertible ops)

Code length / ease

Segment:"Longer, recursive"
Fenwick: "Shorter, iterative, bit magic"

Best for

Segment:"General aggregates, lazy propagation"
Fenwick: Pure point update + range sum problems

Conclusion

Start with Fenwick if the problem is pure range sum + point updates (faster to code, less error-prone). Switch to Segment Tree if you need min/max, range updates, or non-invertible operations.

Edge cases: index 0/1 confusion, negative values/deltas, empty ranges.

For very tight memory, Fenwick wins.