🌳 Fenwick Tree (Binary Indexed Tree – BIT) – Comprehensive Study Guide

The **Fenwick Tree**, also known as the **Binary Indexed Tree (BIT)**, is a **data structure** that allows **efficient range queries & updates** in **O(log n) time**.

⚡ Why Use Fenwick Tree?

  • ✅ **Faster than brute-force O(n) approaches for range queries.**
  • 🚀 **Efficiently computes prefix sums & cumulative frequencies.**
  • 🔄 **Supports both updates & queries in O(log n) time.**
  • 📌 **Used in Competitive Programming & Numerical Computations.**

📌 Understanding Prefix Sums

A **prefix sum** is the sum of elements from the **beginning of the array** up to a certain index. 


                PrefixSum[i] = A[0] + A[1] + ... + A[i]

📌 Difference: Fenwick Tree vs Segment Tree

Feature Fenwick Tree (BIT) Segment Tree
Space Complexity O(n) O(4n)
Query Time O(log n) O(log n)
Update Time O(log n) O(log n)
Range Queries Only **prefix sum queries** Handles **any range-based query**

🛠️ Fenwick Tree Construction & Operations

📌 **1. Initializing a Fenwick Tree**


                vector BIT; 
                int n;
            
                void initializeFenwickTree(int size) {
                    n = size;
                    BIT.assign(n + 1, 0); // BIT[0] is unused
                }

📌 **2. Updating the Fenwick Tree (Point Update – O(log n))**

We **add a value** to an index and propagate it up the tree.


                void updateFenwickTree(int index, int value) {
                    while (index <= n) {
                        BIT[index] += value;
                        index += index & -index; // Move to parent node
                    }
                }

📌 **3. Computing Prefix Sum (O(log n))**

Computes the **sum from index 1 to index i**.


                int prefixSum(int index) {
                    int sum = 0;
                    while (index > 0) {
                        sum += BIT[index];
                        index -= index & -index; // Move to ancestor node
                    }
                    return sum;
                }

📌 **4. Range Sum Query (O(log n))**

Computes the **sum in the range [L, R]**.


                int rangeSum(int left, int right) {
                    return prefixSum(right) - prefixSum(left - 1);
                }

🔄 Fenwick Tree Example

📌 **Example: Constructing & Querying a Fenwick Tree**


                int main() {
                    vector arr = {0, 3, 2, -1, 6, 5, 4, -3, 3, 7, 2};
                    int size = arr.size();
            
                    initializeFenwickTree(size);
                    for (int i = 1; i < size; i++) updateFenwickTree(i, arr[i]);
            
                    cout << "Prefix Sum [1-5]: " << rangeSum(1, 5) << endl;
                    cout << "Prefix Sum [3-7]: " << rangeSum(3, 7) << endl;
            
                    return 0;
                }

⏳ Time Complexity Analysis

Operation Time Complexity
Updating an Index O(log n)
Computing Prefix Sum O(log n)
Computing Range Sum O(log n)

🌍 Real-World Applications of Fenwick Tree

  • 📊 **Cumulative Frequency Counting** – Used in **data analytics & machine learning**.
  • 🎮 **Game Development** – Efficiently handling **score updates**.
  • 📡 **Network Traffic Analysis** – Tracking **real-time metrics**.
  • 📈 **Stock Market Analysis** – Calculating **moving averages**.

🔗 Next Topics