🌳 Binary Indexed Tree (Fenwick Tree) & Segment Tree Tutorial

Introduction

Efficiently answering range queries and updates is a common problem in computer science. Two powerful data structures for this are the Binary Indexed Tree (Fenwick Tree) and the Segment Tree. This tutorial introduces both, explains their use cases, and provides C++ code examples.

---

1. Binary Indexed Tree (Fenwick Tree)

What is it?

A Binary Indexed Tree (BIT), or Fenwick Tree, is a data structure that efficiently supports: - Point updates (add a value to a single element) - Prefix sum queries (sum of the first k elements)

Both operations run in O(log n) time.

Use Cases

• Cumulative frequency tables
• Range sum queries with point updates

Basic Operations

1.1. Initialization

std::vector<int> bit(n + 1, 0); // 1-based indexing

1.2. Update (add value to index)

void update(int idx, int val, std::vector<int>& bit) {
    while (idx < bit.size()) {
        bit[idx] += val;
        idx += idx & -idx;
    }
}

1.3. Query (prefix sum up to index)

int query(int idx, const std::vector<int>& bit) {
    int res = 0;
    while (idx > 0) {
        res += bit[idx];
        idx -= idx & -idx;
    }
    return res;
}

1.4. Example Usage

int n = 10;
std::vector<int> bit(n + 1, 0);
update(3, 5, bit); // add 5 to index 3
int sum = query(3, bit); // sum of elements 1..3

---

2. Segment Tree

What is it?

A Segment Tree is a binary tree data structure that supports: - Range queries (sum, min, max, etc. over a range) - Point or range updates

Both operations run in O(log n) time.

Use Cases

• Range sum/min/max queries
• Range updates (with lazy propagation)

Basic Operations

2.1. Initialization

std::vector<int> seg(4 * n, 0); // 1-based or 0-based

2.2. Build

void build(const std::vector<int>& arr, std::vector<int>& seg, int node, int l, int r) {
    if (l == r) {
        seg[node] = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    build(arr, seg, 2 * node, l, mid);
    build(arr, seg, 2 * node + 1, mid + 1, r);
    seg[node] = seg[2 * node] + seg[2 * node + 1];
}

2.3. Query (sum over [ql, qr])

int query(const std::vector<int>& seg, int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0; // no overlap
    if (ql <= l && r <= qr) return seg[node]; // total overlap
    int mid = (l + r) / 2;
    return query(seg, 2 * node, l, mid, ql, qr) +
           query(seg, 2 * node + 1, mid + 1, r, ql, qr);
}

2.4. Update (add value to index)

void update(std::vector<int>& seg, int node, int l, int r, int idx, int val) {
    if (l == r) {
        seg[node] += val;
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) update(seg, 2 * node, l, mid, idx, val);
    else update(seg, 2 * node + 1, mid + 1, r, idx, val);
    seg[node] = seg[2 * node] + seg[2 * node + 1];
}

2.5. Example Usage

int n = 10;
std::vector<int> arr(n + 1, 0), seg(4 * n, 0);
build(arr, seg, 1, 1, n);
update(seg, 1, 1, n, 3, 5); // add 5 to index 3
int sum = query(seg, 1, 1, n, 1, 3); // sum of elements 1..3

---

3. Comparison

Feature	Binary Indexed Tree	Segment Tree
Code Complexity	Simple	More complex
Memory Usage	O(n)	O(n) or O(4n)
Range Query Types	Prefix sum	Any (sum, min, max)
Range Updates	No (basic)	Yes (with lazy)
Point Updates	Yes	Yes
Typical Use Case	Prefix sums	General range query

---

4. Summary

• Use BIT for simple prefix sums and point updates.
• Use Segment Tree for more complex range queries and updates.

Both are essential tools for competitive programming and efficient algorithm design!