Binary Indexed Tree (BIT) is a data structure that allows efficient queries of a range of elements in an array and updates on individual elements in O(log n) time complexity, where n is the number of elements in the array.
Binary Lifting:
- One of the efficient techniques used to perform search operations in BIT is called Binary lifting.
- Binary Lifting is a technique that helps to navigate through the BIT in O(log n) time complexity. The basic idea of binary lifting is to perform jumps to the next ancestor that covers the range of elements you want to query.
To perform search operations in BIT using binary lifting, we need to store additional information in the BIT, which is the binary representation of the index. For example, if we have an index i, we can write it in binary form as follows:
, where b[k], b[k-1], …, b[0] are binary digits (0 or 1). We store this binary representation in the BIT for each index i.
![i = b[k] * 2^k + b[k-1] * 2^(k-1) + ... + b[0] * 2^0](https://neveropen.co.uk/wp-content/uploads/2024/01/wardslaus-rubhabha_quicklatex.com-7e6c554d78ac14648a969d4ca8d237ba_l3.png "Rendered by QuickLaTeX.com")
, To perform a range query [l, r] in the BIT:
- Find the highest ancestor of r which is also an ancestor of l. We can do this by finding the largest power of 2 that is less than or equal to the distance between l and r.
- We call this power of 2k.
- Then add 2^k to l to move up to the next ancestor.
- We continue this process until we reach r. At each step, we check if the binary digit at the k-th position of r is 1. If it is 1, we include the value of the node at r in the query result.
- Finally, we return the sum of the query result.
Examples:
Input: arr[] = {1, 3, 2, 5, 4}, k = 3
Explanation: The binary representation of the numbers in the range [0, k] are:
- 0: 000
- 1: 001
- 2: 010
- 3: 011
To find the sum of elements in the range [0, k], we can represent the range [0, k] using the binary representation of k. Starting from the most significant bit, if the bit is 1, we include the corresponding prefix sum in the total sum.
Illustration:
- The Binary Indexed Tree (BIT) is a data structure that allows efficient updates and queries on prefix sums of an array. It uses an array of size n to store cumulative sums. Each element of the array represents the sum of certain elements in the original array.
- In binary lifting, we use the binary representation of the index to perform efficient searches in the BIT. By using the binary representation of the index, we can determine which prefix sums to include in the query based on the bits of the index.
Here’s a brief explanation of how the standard BIT implementation works:
- Initialization: The BIT is initialized with all values set to zero.
- Update operation: The update() function is used to modify the value at a specific index i. It increases the value at index i by v and updates the necessary indices to maintain the cumulative frequency property of the BIT. It uses the binary representation of i to determine the indices to update.
- Query operation: The query() function is used to calculate the cumulative sum from index 0 to index i. It traverses the BIT, starting from the index i, following the binary representation of i to find the necessary indices to include in the sum. It accumulates the values of the corresponding indices.
- Range query operation: The range_query() function calculates the sum of values within a given range from index l to index r. It iteratively uses the binary representation of r to determine the necessary indices to include in the sum. It subtracts the cumulative sum from index l-1 to obtain the sum of values within the range.
Here’s an implementation of binary lifting search operations in BIT:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;class BinaryIndexedTree {private: // Declare vector to store the BIT vector<int> tree;public: // Initialize the BIT vector // with zeros BinaryIndexedTree(int n) { tree.resize(n + 1, 0); } void update(int i, int v) { i += 1; // Update the index to the next // node in the BIT while (i < tree.size()) { tree[i] += v; i += i & (-i); } } int query(int i) { i += 1; int res = 0; // Update the index to the // previous node in the BIT while (i > 0) { res += tree[i]; i -= i & (-i); } return res; } int range_query(int l, int r) { int res = 0; while (r >= l) { // Find the largest power of // 2 that is less than or // equal to the distance between // l and r int k = r & (-r); // Include the value of the // node at r in the query // result if the binary digit // at the k-th position // of r is 1 res += (r & k) ? tree[r] : 0; // Move up to the // next ancestor r -= k; } return res; }};// Drivers codeint main(){ int n = 10; BinaryIndexedTree bit(n); // Perform some updates and queries bit.update(0, 1); bit.update(1, 2); bit.update(2, 3); bit.update(3, 4); // Function Calls cout << bit.query(3) << endl; cout << bit.range_query(1, 3) << endl; return 0;} |
Java
// C++ code for the above approach:import java.util.*;class BinaryIndexedTree { private List<Integer> tree; // Initialize the BIT vector // with zeros public BinaryIndexedTree(int n) { tree = new ArrayList<>(n + 1); for (int i = 0; i <= n; i++) { tree.add(0); } } // Update the index to the next // node in the BIT public void update(int i, int v) { i += 1; while (i < tree.size()) { tree.set(i, tree.get(i) + v); i += i & (-i); } } public int query(int i) { i += 1; int res = 0; // Update the index to the // previous node in the BIT while (i > 0) { res += tree.get(i); i -= i & (-i); } return res; } public int rangeQuery(int l, int r) { int res = 0; while (r >= l) { // Find the largest power of // 2 that is less than or // equal to the distance between // l and r int k = r & (-r); // Include the value of the // node at r in the query // result if the binary digit // at the k-th position // of r is 1 res += (r & k) != 0 ? tree.get(r) : 0; r -= k; } return res; } public static void main(String[] args) { int n = 10; BinaryIndexedTree bit = new BinaryIndexedTree(n); // Perform some updates and queries bit.update(0, 1); bit.update(1, 2); bit.update(2, 3); bit.update(3, 4); // Function Calls System.out.println(bit.query(3)); System.out.println(bit.rangeQuery(1, 3)); }} |
Python
# python code for above approachclass BinaryIndexedTree: def __init__(self, n): # Declare list to store the BIT self.tree = [0] * (n + 1) def update(self, i, v): i += 1 # Update the index to the next # node in the BIT while i < len(self.tree): self.tree[i] += v i += i & (-i) def query(self, i): i += 1 res = 0 # Update the index to the # previous node in the BIT while i > 0: res += self.tree[i] i -= i & (-i) return res def range_query(self, l, r): res = 0 while r >= l: # Find the largest power of # 2 that is less than or # equal to the distance between # l and r k = r & (-r) # Include the value of the # node at r in the query # result if the binary digit # at the k-th position # of r is 1 res += self.tree[r] if r & k else 0 # Move up to the # next ancestor r -= k return res# Drivers codedef main(): n = 10 bit = BinaryIndexedTree(n) # Perform some updates and queries bit.update(0, 1) bit.update(1, 2) bit.update(2, 3) bit.update(3, 4) # Function Calls print(bit.query(3)) print(bit.range_query(1, 3))if __name__ == "__main__": main() |
C#
using System;using System.Collections.Generic;class BinaryIndexedTree{ // Declare vector to store the BIT private List<int> tree; // Initialize the BIT vector // with zeros public BinaryIndexedTree(int n) { tree = new List<int>(n + 1); for (int i = 0; i <= n; i++) { tree.Add(0); } } public void Update(int i, int v) { i += 1; // Update the index to the next // node in the BIT while (i < tree.Count) { tree[i] += v; i += i & (-i); } } public int Query(int i) { i += 1; int res = 0; // Update the index to the // previous node in the BIT while (i > 0) { res += tree[i]; i -= i & (-i); } return res; } public int RangeQuery(int l, int r) { int res = 0; while (r >= l) { // Find the largest power of // 2 that is less than or // equal to the distance between // l and r int k = r & (-r); // Include the value of the // node at r in the query // result if the binary digit // at the k-th position // of r is 1 res += (r & k) != 0 ? tree[r] : 0; // Move up to the // next ancestor r -= k; } return res; }}class Program{ // Drivers code static void Main() { int n = 10; BinaryIndexedTree bit = new BinaryIndexedTree(n); bit.Update(0, 1); bit.Update(1, 2); bit.Update(2, 3); bit.Update(3, 4); Console.WriteLine(bit.Query(3)); Console.WriteLine(bit.RangeQuery(1, 3)); }} |
Javascript
class BinaryIndexedTree { constructor(n) { this.tree = new Array(n + 1).fill(0); } update(i, v) { i += 1; while (i < this.tree.length) { this.tree[i] += v; i += i & -i; } } query(i) { i += 1; let res = 0; while (i > 0) { res += this.tree[i]; i -= i & -i; } return res; } range_query(l, r) { let res = 0; while (r >= l) { const k = r & -r; res += (r & k) ? this.tree[r] : 0; r -= k; } return res; }}// Driver codeconst n = 10;const bit = new BinaryIndexedTree(n);// Perform some updates and queriesbit.update(0, 1);bit.update(1, 2);bit.update(2, 3);bit.update(3, 4);// Function callsconsole.log(bit.query(3));console.log(bit.range_query(1, 3)); |
Output
10 6
Time Complexity: O(N * logN).
Auxiliary Space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
