AVL Tree & Binary Indexed Tree (Fenwick Tree)

Part 1: AVL Tree

What is an AVL Tree?

An AVL tree is a self-balancing Binary Search Tree (BST) where for every node, the absolute difference in heights of its left and right subtrees is at most 1. It was the first such data structure, invented by Adelson-Velsky and Landis in 1962.

The guarantee: Because the tree is always balanced, its height is always O(log n), which means search, insert, and delete all run in O(log n) time -- guaranteed, not just on average.

Why Do We Need Balanced BSTs?

A plain BST has O(h) time for operations, where h is the height. If elements are inserted in sorted order, the BST degenerates into a linked list:

An AVL tree rebalances after every insertion to maintain logarithmic height:

Height bound: An AVL tree with n nodes has height at most 1.44 * log2(n). This is very close to the theoretical minimum of log2(n) for a perfectly balanced tree.

Balance Factor

The balance factor of a node is defined as:

BF(node) = height(left subtree) - height(right subtree)

Convention: height of nullptr (empty subtree) = 0; height of a leaf = 1.

AVL invariant: For every node, BF must be in {-1, 0, +1}.

BF = 0 (Valid) 5 3 7 1 6 8 BF(5) = 2−2 = 0. Perfectly balanced.

BF = −2 (INVALID!) 5 7 9 BF(5) = 0−2 = −2. Violation! Need rotation.

When an insertion or deletion causes any node's BF to become +2 or -2, we perform rotations to restore balance.

The Four Rotations

There are exactly four cases of imbalance, each fixed by one or two rotations.

Case 1: Right Rotation (Left-Left / LL Case)

When: BF(node) = +2 AND BF(left child) >= 0

The node is left-heavy, and its left child is also left-heavy (or balanced).

After Right Rotation y x z T1 T2 T3 T4

Steps:

y becomes the new root of this subtree
z becomes y's right child
T3 (y's old right subtree) becomes z's left child
Update heights of z, then y

Case 2: Left Rotation (Right-Right / RR Case)

When: BF(node) = -2 AND BF(right child) <= 0

Mirror of Case 1.

After Left Rotation y z x T1 T2 T3 T4

Steps:

y becomes the new root
z becomes y's left child
T2 (y's old left subtree) becomes z's right child
Update heights of z, then y

Case 3: Left-Right Rotation (LR Case)

When: BF(node) = +2 AND BF(left child) < 0

The node is left-heavy, but its left child is right-heavy. A single right rotation won't fix this -- we need TWO rotations.

After Left Rotate y z x T4 y T3 T1 T2

Right rotate z

Final (balanced) x y z T1 T2 T3 T4

Step 1: Left-rotate around y (y's right child x becomes y's parent) Step 2: Right-rotate around z (x becomes z's parent)

Case 4: Right-Left Rotation (RL Case)

When: BF(node) = -2 AND BF(right child) > 0

Mirror of Case 3.

After Right Rotate y z T1 x T2 y T3 T4

Left rotate z

Final (balanced) x z y T1 T2 T3 T4

Summary of Cases

Complete C++ Implementation

CPP

#include <bits/stdc++.h>
using namespace std;

class AVLTree {
    struct Node {
        int key;
        int height;
        Node *left, *right;
        Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
    };

    Node* root = nullptr;

    // --- Utility functions ---

    int height(Node* n) {
        return n ? n->height : 0;
    }

    int balanceFactor(Node* n) {
        return n ? height(n->left) - height(n->right) : 0;
    }

    void updateHeight(Node* n) {
        n->height = 1 + max(height(n->left), height(n->right));
    }

    // --- Rotations ---

    Node* rotateRight(Node* z) {
        //       z              y
        //      / \            / \
        //     y   T4  =>    x   z
        //    / \               / \
        //   x   T3           T3  T4
        Node* y = z->left;
        Node* T3 = y->right;

        y->right = z;
        z->left = T3;

        updateHeight(z);  // z is now lower, update first
        updateHeight(y);

        return y; // y is the new root of this subtree
    }

    Node* rotateLeft(Node* z) {
        //   z                  y
        //  / \                / \
        // T1  y      =>     z   x
        //    / \            / \
        //   T2  x         T1  T2
        Node* y = z->right;
        Node* T2 = y->left;

        y->left = z;
        z->right = T2;

        updateHeight(z);
        updateHeight(y);

        return y;
    }

    // --- Balance: detect case and apply rotations ---

    Node* balance(Node* n) {
        updateHeight(n);
        int bf = balanceFactor(n);

        // Left-heavy
        if (bf > 1) {
            if (balanceFactor(n->left) < 0)    // LR case
                n->left = rotateLeft(n->left);
            return rotateRight(n);              // LL case (or LR after first rotation)
        }

        // Right-heavy
        if (bf < -1) {
            if (balanceFactor(n->right) > 0)   // RL case
                n->right = rotateRight(n->right);
            return rotateLeft(n);               // RR case (or RL after first rotation)
        }

        return n; // already balanced
    }

    // --- Insert ---

    Node* insert(Node* n, int key) {
        if (!n) return new Node(key);

        if (key < n->key)
            n->left = insert(n->left, key);
        else if (key > n->key)
            n->right = insert(n->right, key);
        else
            return n; // duplicate keys not allowed

        return balance(n);
    }

    // --- Find minimum node in subtree ---

    Node* findMin(Node* n) {
        while (n->left) n = n->left;
        return n;
    }

    // --- Delete ---

    Node* erase(Node* n, int key) {
        if (!n) return nullptr;

        if (key < n->key)
            n->left = erase(n->left, key);
        else if (key > n->key)
            n->right = erase(n->right, key);
        else {
            // Found the node to delete
            if (!n->left || !n->right) {
                // 0 or 1 child
                Node* child = n->left ? n->left : n->right;
                delete n;
                return child; // might be nullptr
            }
            // 2 children: replace with inorder successor
            Node* successor = findMin(n->right);
            n->key = successor->key;
            n->right = erase(n->right, successor->key);
        }

        return balance(n);
    }

    // --- Search ---

    bool search(Node* n, int key) {
        if (!n) return false;
        if (key == n->key) return true;
        if (key < n->key) return search(n->left, key);
        return search(n->right, key);
    }

    // --- Inorder traversal ---

    void inorder(Node* n, vector<int>& result) {
        if (!n) return;
        inorder(n->left, result);
        result.push_back(n->key);
        inorder(n->right, result);
    }

    // --- Print tree structure (for debugging) ---

    void printTree(Node* n, string indent, bool isRight) {
        if (!n) return;
        printTree(n->right, indent + (isRight ? "    " : "|   "), true);
        cout << indent << (isRight ? " /" : " \\") << "-- "
             << n->key << " (h=" << n->height
             << ", bf=" << balanceFactor(n) << ")" << endl;
        printTree(n->left, indent + (isRight ? "|   " : "    "), false);
    }

public:
    void insert(int key) { root = insert(root, key); }
    void erase(int key) { root = erase(root, key); }
    bool search(int key) { return search(root, key); }

    vector<int> inorder() {
        vector<int> result;
        inorder(root, result);
        return result;
    }

    void print() {
        if (root) printTree(root, "", false);
    }
};

int main() {
    AVLTree avl;

    // Insert sequence that would degenerate in a plain BST
    for (int x : {10, 20, 30, 25, 28, 5, 3, 15}) {
        avl.insert(x);
        cout << "After inserting " << x << ":" << endl;
        avl.print();
        cout << endl;
    }

    cout << "Inorder: ";
    for (int x : avl.inorder()) cout << x << " ";
    cout << endl;

    avl.erase(20);
    cout << "\nAfter deleting 20:" << endl;
    avl.print();

    return 0;
}

Step-by-Step Insertion Walkthrough

Insert sequence: 10, 20, 30, 25, 28

Insert 10

    10 (h=1, bf=0)

No imbalance.

Insert 20

    10 (h=2, bf=-1)
      \
       20 (h=1)

BF(10) = 0 - 1 = -1. Still valid.

Insert 30

    10 (h=3, bf=-2)    <-- VIOLATION!
      \
       20 (h=2, bf=-1)
         \
          30

BF(10) = 0 - 2 = -2  -->  Right-heavy
BF(20) = 0 - 1 = -1  -->  RR case

Fix: Left rotate around 10.

       20 (h=2, bf=0)
      /  \
    10    30

Balanced!

Insert 25

       20 (h=3, bf=-1)
      /  \
    10    30 (h=2, bf=1)
         /
        25

BF(30) = 1 - 0 = 1   --> valid
BF(20) = 1 - 2 = -1   --> valid

No imbalance triggered. Tree is valid.

Insert 28

       20 (h=4, bf=-2)     <-- VIOLATION!
      /  \
    10    30 (h=3, bf=2)   <-- also VIOLATION
         /
        25 (h=2, bf=-1)
          \
           28

Fix bottom-up. First imbalanced ancestor from the inserted node is 30.

BF(30) = 2, BF(25) = -1  -->  LR case at node 30!

Step 1: Left rotate around 25:
       20
      /  \
    10    30
         /
        28
       /
      25

Step 2: Right rotate around 30:
       20
      /  \
    10    28
         / \
        25  30

Now check BF(20): h(left)=1, h(right)=2, BF=-1. Valid!

Final tree:
         20
        /  \
      10    28
           / \
          25  30

Complexity Analysis

Height bound: For n nodes, height h satisfies:

h <= 1.4405 * log2(n + 2) - 0.3277

Approximately: h ~ 1.44 * log2(n)

This is tighter than a red-black tree (h <= 2 * log2(n + 1)), meaning AVL trees are more rigidly balanced and have faster lookups on average, but may do more rotations on insert/delete.

Rotations per operation:

Insert: at most 2 rotations (one single or one double)
Delete: up to O(log n) rotations (rebalancing may propagate to the root)

AVL vs Red-Black Tree vs Splay Tree

AVL trees are preferred when lookups dominate. Red-black trees are preferred when inserts/deletes are frequent (fewer rotations).

Part 2: Binary Indexed Tree (Fenwick Tree)

The Problem

Given an array a[1..n], we need to support two operations efficiently:

Point Update: Add a value delta to a[i] (i.e., a[i] += delta)
Prefix Sum Query: Compute a[1] + a[2] + ... + a[i]

(Range sum a[l..r] = prefix(r) - prefix(l-1), so prefix sums suffice.)

Naive approaches:

Approach	Update	Query
Plain array	O(1)	O(n)
Prefix sum array	O(n) (rebuild)	O(1)

Binary Indexed Tree: O(log n) for both! And the implementation is shockingly simple.

The Key Insight: Binary Representation

The BIT (also called Fenwick Tree, after Peter Fenwick who described it in 1994) exploits the binary representation of indices.

The lowbit function:

lowbit(x) = x & (-x)

This extracts the lowest set bit of x. Since -x in two's complement is ~x + 1, the AND preserves only the rightmost 1-bit.

x = 12 = 1100₂  -->  lowbit = 0100₂ = 4
x = 10 = 1010₂  -->  lowbit = 0010₂ = 2
x = 6  = 0110₂  -->  lowbit = 0010₂ = 2
x = 8  = 1000₂  -->  lowbit = 1000₂ = 8
x = 7  = 0111₂  -->  lowbit = 0001₂ = 1
x = 1  = 0001₂  -->  lowbit = 0001₂ = 1

The rule:

BIT[i] stores the sum of a range of lowbit(i) elements ending at index i.
Specifically: BIT[i] = a[i - lowbit(i) + 1] + a[i - lowbit(i) + 2] + ... + a[i]

How BIT Works -- The Structure

Array (1-indexed): a[1]=1, a[2]=3, a[3]=2, a[4]=5, a[5]=1, a[6]=4, a[7]=2, a[8]=3

Visualizing as a Tree

Each node i is responsible for a range of lowbit(i) elements. The parent-child relationship in the BIT forms a tree:

Query: Computing Prefix Sum

To compute prefix_sum(i) = a[1] + a[2] + ... + a[i]:

Algorithm: Start at index i. Add BIT[i] to the result. Strip the lowest bit (i -= lowbit(i)). Repeat until i = 0.

Why this works: Stripping the lowest bit moves us to the previous non-overlapping range. The ranges we visit together cover exactly a[1..i].

Walkthrough: prefix_sum(7)

i = 7 = 0111₂
  Add BIT[7] = 2        (covers a[7])
  i -= lowbit(7) = i -= 1 = 6

i = 6 = 0110₂
  Add BIT[6] = 5        (covers a[5..6])
  i -= lowbit(6) = i -= 2 = 4

i = 4 = 0100₂
  Add BIT[4] = 11       (covers a[1..4])
  i -= lowbit(4) = i -= 4 = 0

i = 0  -->  STOP

Result = 2 + 5 + 11 = 18
Check: a[1]+a[2]+...+a[7] = 1+3+2+5+1+4+2 = 18  Correct!

Number of iterations: Equal to the number of set bits in i, which is at most log2(n). So prefix query is O(log n).

Walkthrough: prefix_sum(5)

i = 5 = 0101₂
  Add BIT[5] = 1        (covers a[5])
  i -= 1 = 4

i = 4 = 0100₂
  Add BIT[4] = 11       (covers a[1..4])
  i -= 4 = 0

Result = 1 + 11 = 12
Check: 1+3+2+5+1 = 12  Correct!

Update: Point Add

To add delta to position p:

Algorithm: Start at index p. Add delta to BIT[p]. Add the lowest bit (p += lowbit(p)). Repeat until p > n.

Why this works: Adding the lowest bit moves us to the parent in the BIT tree. Every ancestor's range includes position p, so they all need updating.

Walkthrough: update(3, +5) (add 5 to a[3])

p = 3 = 011₂
  BIT[3] += 5           (BIT[3] covers a[3])
  p += lowbit(3) = p += 1 = 4

p = 4 = 100₂
  BIT[4] += 5           (BIT[4] covers a[1..4], includes a[3])
  p += lowbit(4) = p += 4 = 8

p = 8 = 1000₂
  BIT[8] += 5           (BIT[8] covers a[1..8], includes a[3])
  p += lowbit(8) = p += 8 = 16

p = 16 > 8 = n  -->  STOP

Updated 3 nodes. O(log n) time.

Complete C++ Implementation

CPP

#include <bits/stdc++.h>
using namespace std;

class BIT {
    vector<int> tree;
    int n;

public:
    // Initialize with size n (1-indexed)
    BIT(int n) : n(n), tree(n + 1, 0) {}

    // Build from an existing array in O(n) time
    BIT(vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
        // O(n) construction using the "propagate up" trick
        for (int i = 1; i <= n; i++) {
            tree[i] += arr[i - 1];
            int parent = i + (i & (-i));
            if (parent <= n)
                tree[parent] += tree[i];
        }
    }

    // Point update: add delta to position i (1-indexed)
    void update(int i, int delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    // Prefix sum: sum of a[1..i]
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }

    // Range sum: sum of a[l..r] (1-indexed)
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    // Point query: get value of a[i] in O(log n)
    // (Useful when you only store deltas)
    int pointQuery(int i) {
        return query(i, i);
    }
};

int main() {
    vector<int> arr = {1, 3, 2, 5, 1, 4, 2, 3};
    BIT bit(arr);

    cout << "Sum [1..7] = " << bit.query(7) << endl;       // 18
    cout << "Sum [3..6] = " << bit.query(3, 6) << endl;    // 12
    cout << "Sum [1..8] = " << bit.query(8) << endl;       // 21

    bit.update(3, 5); // a[3] += 5, now a[3] = 7

    cout << "After a[3] += 5:" << endl;
    cout << "Sum [1..7] = " << bit.query(7) << endl;       // 23
    cout << "Sum [3..6] = " << bit.query(3, 6) << endl;    // 17

    return 0;
}

O(n) Construction Explained

The naive way to build a BIT from an array is to call update for each element: O(n log n). But we can do it in O(n):

For each index i from 1 to n:
  1. Set tree[i] += arr[i-1]          (add the array element)
  2. Let parent = i + lowbit(i)
  3. If parent <= n, set tree[parent] += tree[i]

This propagates each element to its immediate parent only.
Each element gets accumulated upward exactly once.

Why it works: After processing index i, tree[i] contains the correct sum for its range. Adding tree[i] to its parent's running total is sufficient because the parent's range is the union of its children's ranges.

Processing order for n=8:
  i=1: tree[1]=1, parent=2: tree[2]+=1 -> tree[2]=1
  i=2: tree[2]+=3=4, parent=4: tree[4]+=4 -> tree[4]=4
  i=3: tree[3]=2, parent=4: tree[4]+=2 -> tree[4]=6
  i=4: tree[4]+=5=11, parent=8: tree[8]+=11 -> tree[8]=11
  i=5: tree[5]=1, parent=6: tree[6]+=1 -> tree[6]=1
  i=6: tree[6]+=4=5, parent=8: tree[8]+=5 -> tree[8]=16
  i=7: tree[7]=2, parent=8: tree[8]+=2 -> tree[8]=18
  i=8: tree[8]+=3=21, parent=16: out of bounds

Final: tree = [_, 1, 4, 2, 11, 1, 5, 2, 21]  (index 0 unused)
Matches our earlier calculation!

Range Update + Point Query

Sometimes we need:

Range update: Add delta to all elements in a[l..r]
Point query: What is a[i]?

Trick: Store a difference array in the BIT.

To add delta to a[l..r]:
  bit.update(l, +delta)
  bit.update(r+1, -delta)

To get a[i]:
  bit.query(i)  // prefix sum of difference array = actual value

CPP

class RangeUpdatePointQuery {
    BIT bit;
public:
    RangeUpdatePointQuery(int n) : bit(n) {}

    void rangeAdd(int l, int r, int delta) {
        bit.update(l, delta);
        bit.update(r + 1, -delta);
    }

    int pointQuery(int i) {
        return bit.query(i);
    }
};

Range Update + Range Query

Need both range updates and range queries? Use two BITs.

Mathematical derivation:

After adding delta to a[l..r], the prefix sum up to index p changes by:

If p < l: no change
If l <= p <= r: change = delta * (p - l + 1)
If p > r: change = delta * (r - l + 1)

We maintain two BITs, B1 and B2, where:

prefix_sum(p) = B1.query(p) * p - B2.query(p)

For range add delta to [l, r]:

B1.update(l, delta);       B1.update(r+1, -delta);
B2.update(l, delta*(l-1)); B2.update(r+1, -delta*r);

CPP

class RangeUpdateRangeQuery {
    int n;
    BIT b1, b2;
    vector<long long> prefix; // original prefix sums

public:
    RangeUpdateRangeQuery(vector<int>& arr)
        : n(arr.size()), b1(n), b2(n), prefix(n + 1, 0) {
        for (int i = 1; i <= n; i++)
            prefix[i] = prefix[i-1] + arr[i-1];
    }

    void rangeAdd(int l, int r, long long delta) {
        b1.update(l, delta);
        b1.update(r + 1, -delta);
        b2.update(l, delta * (l - 1));
        b2.update(r + 1, -delta * r);
    }

    long long prefixSum(int p) {
        return prefix[p] + (long long)b1.query(p) * p - b2.query(p);
    }

    long long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

2D Binary Indexed Tree

For a 2D matrix, support:

Point update at (x, y)
Prefix sum query for the rectangle (1,1) to (x,y)

Simply nest the 1D operations:

CPP

class BIT2D {
    vector<vector<int>> tree;
    int rows, cols;

public:
    BIT2D(int r, int c) : rows(r), cols(c), tree(r + 1, vector<int>(c + 1, 0)) {}

    void update(int x, int y, int delta) {
        for (int i = x; i <= rows; i += i & (-i))
            for (int j = y; j <= cols; j += j & (-j))
                tree[i][j] += delta;
    }

    int query(int x, int y) {
        int sum = 0;
        for (int i = x; i > 0; i -= i & (-i))
            for (int j = y; j > 0; j -= j & (-j))
                sum += tree[i][j];
        return sum;
    }

    // Rectangle sum query: (x1,y1) to (x2,y2)
    int query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1-1, y2)
             - query(x2, y1-1) + query(x1-1, y1-1);
    }
};

Time: O(log n * log m) per operation.

Classic Problems

1. Range Sum Query - Mutable (LeetCode 307)

CPP

class NumArray {
    vector<int> tree;
    vector<int> nums;
    int n;

    void add(int i, int delta) {
        for (i++; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    int prefixSum(int i) {
        int s = 0;
        for (i++; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }

public:
    NumArray(vector<int>& nums) : nums(nums), n(nums.size()), tree(nums.size() + 1, 0) {
        for (int i = 0; i < n; i++)
            add(i, nums[i]);
    }

    void update(int index, int val) {
        add(index, val - nums[index]);
        nums[index] = val;
    }

    int sumRange(int left, int right) {
        return prefixSum(right) - (left > 0 ? prefixSum(left - 1) : 0);
    }
};

2. Count of Smaller Numbers After Self (LeetCode 315)

Problem: For each element, count how many elements to its right are smaller.

Approach: Process from right to left. Use a BIT indexed by value (after coordinate compression). For each element, query the prefix sum up to value - 1, then insert the current value.

CPP

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        // Coordinate compression
        vector<int> sorted_nums = nums;
        sort(sorted_nums.begin(), sorted_nums.end());
        sorted_nums.erase(unique(sorted_nums.begin(), sorted_nums.end()), sorted_nums.end());
        int m = sorted_nums.size();

        auto getIdx = [&](int val) {
            return lower_bound(sorted_nums.begin(), sorted_nums.end(), val) - sorted_nums.begin() + 1;
        };

        // BIT
        vector<int> tree(m + 1, 0);
        auto update = [&](int i) {
            for (; i <= m; i += i & (-i)) tree[i]++;
        };
        auto query = [&](int i) -> int {
            int s = 0;
            for (; i > 0; i -= i & (-i)) s += tree[i];
            return s;
        };

        vector<int> result(n);
        for (int i = n - 1; i >= 0; i--) {
            int idx = getIdx(nums[i]);
            result[i] = query(idx - 1); // count elements smaller than nums[i]
            update(idx);                 // insert nums[i]
        }
        return result;
    }
};

3. Inversion Count

Problem: Count pairs (i, j) where i < j and a[i] > a[j].

Same approach as problem 2: process left to right, and for each element query how many previously inserted elements are larger.

CPP

long long inversionCount(vector<int>& arr) {
    int n = arr.size();
    // Coordinate compression
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());
    int m = sorted_arr.size();

    auto getIdx = [&](int val) {
        return lower_bound(sorted_arr.begin(), sorted_arr.end(), val) - sorted_arr.begin() + 1;
    };

    vector<int> tree(m + 1, 0);
    auto update = [&](int i) { for (; i <= m; i += i & (-i)) tree[i]++; };
    auto query = [&](int i) -> int {
        int s = 0; for (; i > 0; i -= i & (-i)) s += tree[i]; return s;
    };

    long long count = 0;
    for (int i = 0; i < n; i++) {
        int idx = getIdx(arr[i]);
        count += i - query(idx); // elements before i that are > arr[i]
        update(idx);
    }
    return count;
}

BIT vs Segment Tree

*Via query(r) - query(l-1), requires an invertible operation (addition has inverse subtraction).

**Using the difference array trick for range add + point query, or two BITs for range add + range query.

Rule of thumb:

If you only need prefix sums with point updates: use BIT (simpler, faster).
If you need min/max, arbitrary range operations, or range update + range query with lazy propagation: use segment tree.

Summary

AVL Tree: A height-balanced BST guaranteeing O(log n) operations through 4 rotation patterns (LL, RR, LR, RL). More rigidly balanced than red-black trees, making lookups faster at the cost of slightly more rotation work during modifications.

Binary Indexed Tree: An elegant data structure that uses binary arithmetic to achieve O(log n) point updates and prefix queries with minimal code and memory. The key operations (i += i & (-i) for update, i -= i & (-i) for query) are beautifully simple yet powerful enough to solve a wide range of problems from range sums to inversion counting.