"# Introduction To Fenwick Tree (Binary Indexed Tree)\n\n\n\n\n\nUnlock the power of efficient range queries and updates with the Fenwick Tree, also known as the Binary Indexed Tree (BIT). This guide provides a comprehensive, beginner-friendly introduction to this powerful data structure, enabling you to solve complex problems with ease. Learn how it works, how to implement it in C++, and how to apply it to real-world scenarios.\n\n**What You'll Learn:**\n\n* Understand the core concepts of the Fenwick Tree (Binary Indexed Tree).\n* Implement a Fenwick Tree in C++ from scratch.\n* Perform efficient range sum queries and updates.\n* Apply the Fenwick Tree to solve real-world problems.\n* Analyze the time and space complexity of Fenwick Tree operations.\n* Identify situations where a Fenwick Tree is the optimal choice.\n\n## Why Learn Fenwick Tree?\n\nImagine you have a massive array and frequently need to calculate the sum of elements within a specific range, or update individual elements. A naive approach of iterating through the array for each query would be incredibly slow, especially with frequent updates. The Fenwick Tree solves this problem elegantly. It allows you to perform both range sum queries and element updates in logarithmic time, making it significantly faster than brute-force methods. This efficiency is crucial in many applications, from data analysis to competitive programming. Mastering the Fenwick Tree will equip you with a valuable tool for optimizing your algorithms and tackling complex challenges.\n\n## Prerequisites\n\n* Basic understanding of arrays and binary representation.\n* Familiarity with C++ syntax and data structures (vectors).\n\n## What is a Fenwick Tree (Binary Indexed Tree)?\n\nA Fenwick Tree, or Binary Indexed Tree (BIT), is a data structure used for efficiently calculating prefix sums and updating elements in an array. Unlike a traditional tree structure, the Fenwick Tree is implicitly represented using an array. Each element in the Fenwick Tree array stores the sum of a specific range of elements from the original array. The key idea behind the Fenwick Tree is to leverage the binary representation of indices to efficiently navigate and update the tree.\n\n**Key Features:**\n\n* **Efficient Range Sum Queries:** Allows for calculating the sum of elements within a specified range in logarithmic time, O(log n).\n* **Efficient Updates:** Enables updating individual elements in the array and propagating the changes throughout the tree in logarithmic time, O(log n).\n* **Space Efficiency:** Requires only O(n) space, where n is the size of the original array.\n* **Simple Implementation:** Relatively easy to implement compared to other advanced data structures like segment trees.\n\n## How Does a Fenwick Tree Work?\n\nThe Fenwick Tree relies on the binary representation of array indices to efficiently store and retrieve cumulative sums. Let's break down the core concepts:\n\n**1. Lowbit Function:**\n\nThe `lowbit` function is the cornerstone of the Fenwick Tree. It calculates the value of the least significant bit (LSB) of a number. In other words, it finds the smallest power of 2 that divides the number.\n\n```c++\n#include \nusing namespace std;\n\nint lowbit(int x) {\n return x & (-x);\n}\n```\n\n**Example:**\n\n* `lowbit(6)` (binary `110`) = `2` (binary `010`)\n* `lowbit(12)` (binary `1100`) = `4` (binary `0100`)\n\n**2. Tree Representation:**\n\nThe Fenwick Tree is represented as an array, `tree`, of the same size as the original array, `arr`, plus one (indexed from 1). `tree[i]` stores the sum of elements in `arr` within a specific range, determined by the `lowbit` of `i`.\n\n**3. Update Operation:**\n\nWhen an element in the original array is updated, we need to update the corresponding nodes in the Fenwick Tree. The update operation involves traversing the tree upwards, adding the update value to all nodes that are affected by the change.\n\n**Algorithm for Update (add `val` to `arr[i]`):**\n\n1. Start at index `i + 1` in the `tree` array (since the tree is 1-indexed).\n2. Add `val` to `tree[i]`.\n3. Move to the next index by adding `lowbit(i)` to `i`.\n4. Repeat steps 2 and 3 until `i` exceeds the size of the `tree` array.\n\n**4. Query Operation:**\n\nThe query operation calculates the prefix sum up to a given index. It involves traversing the tree downwards, summing the values of the nodes that contribute to the prefix sum.\n\n**Algorithm for Query (calculate sum from `arr[0]` to `arr[i]`):**\n\n1. Start at index `i + 1` in the `tree` array.\n2. Initialize `sum` to 0.\n3. Add `tree[i]` to `sum`.\n4. Move to the previous index by subtracting `lowbit(i)` from `i`.\n5. Repeat steps 3 and 4 until `i` becomes 0.\n6. Return `sum`.\n\n## C++ Implementation of Fenwick Tree\n\n```c++\n#include \n#include \nusing namespace std;\n\nclass FenwickTree {\npublic:\n FenwickTree(const vector& arr) : n(arr.size()), tree(n + 1, 0) {\n // Build the Fenwick Tree based on the input array.\n for (int i = 0; i < n; ++i) {\n update(i, arr[i]); // Initialize the tree with the array values.\n }\n }\n\n // Updates the value at index i by adding 'val' to it.\n void update(int i, int val) {\n i++; // Fenwick Tree is 1-indexed\n while (i <= n) {\n tree[i] += val;\n i += lowbit(i);\n }\n }\n\n // Returns the prefix sum from index 0 to i (inclusive).\n int getSum(int i) {\n i++; // Fenwick Tree is 1-indexed\n int sum = 0;\n while (i > 0) {\n sum += tree[i];\n i -= lowbit(i);\n }\n return sum;\n }\n\n // Returns the sum of elements in the range [left, right] (inclusive).\n int rangeSum(int left, int right) {\n return getSum(right) - getSum(left - 1);\n }\n\nprivate:\n int n; // Size of the original array.\n vector tree; // The Fenwick Tree array.\n\n // Calculates the least significant bit (LSB) of x.\n int lowbit(int x) {\n return x & (-x);\n }\n};\n\nint main() {\n vector arr = {2, 4, 5, 7, 8, 9, 1, 6};\n FenwickTree ft(arr);\n\n cout << \"Sum of elements from index 0 to 5: \" << ft.getSum(5) << endl; // Output: 35\n cout << \"Sum of elements from index 2 to 6: \" << ft.rangeSum(2, 6) << endl; // Output: 30\n\n ft.update(3, 6); // Update arr[3] from 7 to 13 (add 6 to it)\n cout << \"Updated sum of elements from index 0 to 5: \" << ft.getSum(5) << endl; // Output: 41\n cout << \"Updated sum of elements from index 2 to 6: \" << ft.rangeSum(2, 6) << endl; // Output: 36\n\n return 0;\n}\n```\n\n**Explanation:**\n\n* **`FenwickTree(const vector& arr)`:** The constructor initializes the Fenwick Tree with the given array. It iterates through the input array and uses the `update()` function to populate the tree.\n* **`update(int i, int val)`:** This function updates the value at index `i` by adding `val` to it. The `while` loop traverses the tree upwards, updating all affected nodes. Notice the `i++` to account for the 1-based indexing of the Fenwick Tree.\n* **`getSum(int i)`:** This function calculates the prefix sum from index 0 to `i`. The `while` loop traverses the tree downwards, summing the values of the contributing nodes. Again, `i++` handles the 1-based indexing.\n* **`rangeSum(int left, int right)`:** Calculates the sum of elements within the range \\[left, right] by subtracting the prefix sum up to `left - 1` from the prefix sum up to `right`.\n* **`lowbit(int x)`:** This function calculates the least significant bit (LSB) of `x`, as explained previously.\n\n## Practical Examples\n\nLet's explore some real-world applications of the Fenwick Tree:\n\n**1. Range Queries in Data Streams:**\n\nImagine you are processing a stream of data, such as website traffic or sensor readings. You need to efficiently calculate the sum of values within a specific time window. A Fenwick Tree allows you to update the stream with new data points and query the sum within a range in real-time.\n\n**2. Image Processing:**\n\nIn image processing, you might need to calculate the sum of pixel intensities within a region of interest. A 2D Fenwick Tree (explained in the Advanced Section) can be used to efficiently perform these calculations.\n\n**3. Online Judge Problems (Competitive Programming):**\n\nFenwick Trees are frequently used in competitive programming contests to solve problems involving range queries and updates. For example, problems that involve finding the number of inversions in an array or calculating the number of elements within a given range can be efficiently solved using a Fenwick Tree.\n\n**Example: Counting Inversions**\n\nAn inversion in an array `arr` is a pair of indices `(i, j)` such that `i < j` and `arr[i] > arr[j]`. Counting inversions is a classic problem solvable with a Fenwick Tree. The general approach involves iterating through the array, and for each element `arr[i]`, counting the number of elements `arr[j]` that are smaller than `arr[i]` and appear before `arr[i]` in the array. This can be done efficiently by sorting the array, and then using the Fenwick Tree to track how many elements smaller than `arr[i]` have already been seen.\n\n```c++\n#include \n#include \n#include \nusing namespace std;\n\nint countInversions(vector& arr) {\n int n = arr.size();\n vector sortedArr = arr;\n sort(sortedArr.begin(), sortedArr.end());\n map rankMap;\n int rank = 1;\n for (int i = 0; i < n; ++i) {\n if (rankMap.find(sortedArr[i]) == rankMap.end()) {\n rankMap[sortedArr[i]] = rank++;\n }\n }\n\n FenwickTree ft(vector(n, 0)); // Initialize with a zero-filled array of size n\n int inversions = 0;\n\n for (int i = n - 1; i >= 0; --i) {\n inversions += ft.getSum(rankMap[arr[i]] - 2); // Count elements smaller than arr[i]\n ft.update(rankMap[arr[i]] - 1, 1); // Mark that we've seen arr[i]\n }\n\n return inversions;\n}\n\nint main() {\n vector arr = {8, 4, 2, 1};\n cout << \"Number of inversions: \" << countInversions(arr) << endl; // Output: 6\n\n vector arr2 = {3, 1, 2};\n cout << \"Number of inversions: \" << countInversions(arr2) << endl; // Output: 2\n\n return 0;\n}\n```\n\n## Advanced Section: 2D Fenwick Tree and Performance Considerations\n\n**1. 2D Fenwick Tree:**\n\nA Fenwick Tree can be extended to handle 2D arrays. Instead of a 1D array, you would have a 2D `tree` array. The `update` and `getSum` functions would need to be modified to iterate over both dimensions. This is useful for problems that involve range queries and updates on a 2D grid, such as calculating the sum of pixel intensities within a rectangular region in an image.\n\n```c++\n#include \n#include \nusing namespace std;\n\n// Example of a 2D update function (simplified)\nvoid update2D(vector>& tree, int x, int y, int val, int n, int m) {\n for (; x <= n; x += lowbit(x)) {\n for (int y1 = y; y1 <= m; y1 += lowbit(y1)) {\n tree[x][y1] += val;\n }\n }\n}\n\n// Example of a 2D getSum function (simplified)\nint getSum2D(vector>& tree, int x, int y) {\n int sum = 0;\n for (; x > 0; x -= lowbit(x)) {\n for (int y1 = y; y1 > 0; y1 -= lowbit(y1)) {\n sum += tree[x][y1];\n }\n }\n return sum;\n}\n\n// Helper function (same as before)\nint lowbit(int x) {\n return x & (-x);\n}\n\nint main() {\n int n = 3, m = 3;\n vector> grid(n + 1, vector(m + 1, 0)); // Initialize grid\n vector> tree(n + 1, vector(m + 1, 0)); // Initialize Fenwick tree\n\n // Example usage: Update grid[1][1] with value 5\n update2D(tree, 1, 1, 5, n, m);\n\n // Get sum from grid[0][0] to grid[1][1] (inclusive, but tree is 1-indexed)\n cout << \"Sum from (0,0) to (0,0): \" << getSum2D(tree, 1, 1) << endl; // Output: 5\n\n return 0;\n}\n```\n\n**2. Performance Considerations:**\n\n* **Time Complexity:** Both `update` and `getSum` operations have a time complexity of O(log n), where n is the size of the array (or the dimensions of the 2D array in the case of a 2D Fenwick Tree).\n* **Space Complexity:** The Fenwick Tree requires O(n) space, which is relatively efficient.\n* **Comparison with Segment Tree:** While Segment Trees can handle more complex queries (e.g., finding the minimum or maximum within a range), Fenwick Trees are generally faster and easier to implement for range sum queries and updates.\n* **When to Use:** Fenwick Trees are best suited for problems that involve frequent range sum queries and updates on a static array. If the array is modified heavily, or if more complex queries are required, a Segment Tree might be a better choice.\n\n**3. Common Pitfalls and Solutions:**\n\n* **Off-by-One Errors:** Remember that the Fenwick Tree is typically 1-indexed, so you need to adjust the indices accordingly when accessing the `tree` array.\n* **Integer Overflow:** When calculating sums, be careful of potential integer overflows, especially if the array contains large values. Use `long long` data type if necessary.\n* **Incorrect `lowbit` Implementation:** Make sure your `lowbit` function is implemented correctly. A common mistake is to forget the parentheses around `-x`.\n\n## FAQ Section\n\n**Q: What is the difference between a Fenwick Tree and a Segment Tree?**\n\nA: Both Fenwick Trees and Segment Trees are used for range queries and updates, but they differ in their complexity and capabilities. Segment Trees can handle more complex queries like finding the minimum or maximum in a range but are more complex to implement and have a slightly higher constant factor in their time complexity. Fenwick Trees are simpler to implement and generally faster for range sum queries and updates.\n\n**Q: When should I use a Fenwick Tree instead of a Segment Tree?**\n\nA: Use a Fenwick Tree when you need to perform frequent range sum queries and updates on an array, and the simplicity and speed of implementation are important. If you need to perform more complex queries (e.g., finding the minimum or maximum in a range), or if the array is modified heavily, a Segment Tree might be a better choice. Fenwick Trees are generally preferred for problems where you primarily need prefix sums and updates.\n\n**Q: How do I handle negative values in the array when using a Fenwick Tree?**\n\nA: Fenwick Trees can handle negative values without any modification to the core algorithm. The `update` and `getSum` functions will work correctly with negative values.\n\n**Q: Can I use a Fenwick Tree to find the minimum or maximum value in a range?**\n\nA: No, the standard Fenwick Tree is designed for range sum queries. To find the minimum or maximum value in a range, you would typically use a Segment Tree or other specialized data structures. While it's *possible* to adapt a Fenwick Tree for min/max queries, it's not its intended purpose and would likely be less efficient than a Segment Tree.\n\n**Q: How can I optimize the memory usage of a Fenwick Tree?**\n\nA: The Fenwick Tree inherently uses O(n) space, which is already quite efficient. There isn't much room for further optimization in terms of space complexity. However, you can ensure that you are using the appropriate data type for the `tree` array to avoid unnecessary memory consumption. For example, if the array values are small integers, you can use `int` instead of `long long`.\n\n## Reference Video\n\n[Watch the reference video](https://youtu.be/CWDQJGaN1gY)\n\n## Conclusion\n\nThe Fenwick Tree (Binary Indexed Tree) is a powerful and versatile data structure that provides efficient solutions for range sum queries and updates. Its simplicity and speed make it a valuable tool for solving a wide range of problems in data analysis, image processing, and competitive programming. By understanding the core concepts and mastering the implementation, you can leverage the Fenwick Tree to optimize your algorithms and tackle complex challenges with ease.\n\n**Next Steps:**\n\n* Practice implementing the Fenwick Tree from scratch on various coding platforms.\n* Solve problems that involve range queries and updates to solidify your understanding.\n* Explore advanced applications of the Fenwick Tree, such as 2D Fenwick Trees and their uses in image processing.\n* Compare the performance of Fenwick Trees with other data structures like Segment Trees to understand their trade-offs.\n\n**Practical Exercises:**\n\n1. **Implement `rangeUpdate(left, right, val)`:** Add a function to the `FenwickTree` class that allows you to update all elements in the range `[left, right]` by adding `val` to them.\n2. **Solve \"Range Sum Query - Mutable\" on LeetCode:** This is a classic problem where you can apply the Fenwick Tree to efficiently handle range sum queries and updates.\n3. **Implement a 2D Fenwick Tree:** Extend the given 2D update and getSum functions into a fully functional 2D Fenwick Tree class.\n\n```c++\n#include \n#include \nusing namespace std;\n\nclass FenwickTree {\npublic:\n FenwickTree(const vector& arr) : n(arr.size()), tree(n + 1, 0), originalArray(arr) {\n // Build the Fenwick Tree based on the input array.\n for (int i = 0; i < n; ++i) {\n update(i, arr[i]); // Initialize the tree with the array values.\n }\n }\n\n // Updates the value at index i by adding 'val' to it.\n void update(int i, int val) {\n int diff = val - originalArray[i]; //Calculate the difference\n originalArray[i] = val; //Update original array\n\n i++; // Fenwick Tree is 1-indexed\n while (i <= n) {\n tree[i] += diff;\n i += lowbit(i);\n }\n }\n\n // Returns the prefix sum from index 0 to i (inclusive).\n int getSum(int i) {\n i++; // Fenwick Tree is 1-indexed\n int sum = 0;\n while (i > 0) {\n sum += tree[i];\n i -= lowbit(i);\n }\n return sum;\n }\n\n // Returns the sum of elements in the range [left, right] (inclusive).\n int rangeSum(int left, int right) {\n return getSum(right) - getSum(left - 1);\n }\n\n //Updates the range from left to right (inclusive) by adding val to each element\n void rangeUpdate(int left, int right, int val) {\n for(int i = left; i <= right; ++i){\n update(i, originalArray[i] + val);\n }\n }\n\nprivate:\n int n; // Size of the original array.\n vector tree; // The Fenwick Tree array.\n vector originalArray; //The original array\n // Calculates the least significant bit (LSB) of x.\n int lowbit(int x) {\n return x & (-x);\n }\n};\n\nint main() {\n vector arr = {2, 4, 5, 7, 8, 9, 1, 6};\n FenwickTree ft(arr);\n\n cout << \"Original array: \";\n for(int i = 0; i < arr.size(); ++i){\n cout << arr[i] << \" \";\n }\n cout << endl;\n\n cout << \"Sum of elements from index 0 to 5: \" << ft.getSum(5) << endl;\n cout << \"Sum of elements from index 2 to 6: \" << ft.rangeSum(2, 6) << endl;\n\n ft.rangeUpdate(1, 3, 2);\n cout << \"Array after range update (add 2 to elements from index 1 to 3):\" << endl;\n\n cout << \"Updated sum of elements from index 0 to 5: \" << ft.getSum(5) << endl;\n cout << \"Updated sum of elements from index 2 to 6: \" << ft.rangeSum(2, 6) << endl;\n\n return 0;\n}\n\n"