We’ll first break down the steps to find and remove the rightmost set bit, then discuss how these operations are used in Fenwick Trees for efficient updates and queries.
Let’s start with finding and removing the rightmost set bit from a number. Suppose we have a binary number x = 10011000.
a1bAny binary number can be broken down into three parts:
a is the part before the rightmost set bit.1 is the rightmost set bit.b is the part after the rightmost set bit (which will be a sequence of zeros).For x = 10011000, we can write it as:
a = 1001 (the part before the rightmost set bit),1 = 1 (the rightmost set bit),b = 000 (the part after the rightmost set bit).So, x = a1b.
-xNext, we calculate the two's complement of x, which is -x. The two's complement flips the bits of x and adds 1.
For x = 10011000, -x is calculated as:
x' = 011001111: -x = 01100111 + 1 = 01101000Now, to find the rightmost set bit, we use the operation x & -x.
For x = 10011000 and -x = 01101000:
x & -x = 10011000 & 01101000 = 00001000
This operation isolates the rightmost set bit, which in this case is 00001000 (or 8 in decimal).
To remove the rightmost set bit from x, we perform:
x = x - (x & -x)
In our example, x = 10011000 and x & -x = 00001000:
x - (x & -x) = 10011000 - 00001000 = 10010000
So, after removing the rightmost set bit, x = 10010000.
Fenwick Trees (Binary Indexed Trees) store prefix sums, and their structure allows efficient updates and range sum queries. Each index in the tree covers a specific range of values based on the binary representation of the index.
For any index i in the Fenwick Tree, the range of numbers it covers is determined by removing the last set bit from i.
For example, let’s take i = 13:
i = 13 is 1101 in binary.12 (1100).13 is from 12 + 1 to 13, i.e., the range [13, 13].When we update the value at a specific index i, we need to propagate this update to all subsequent indices whose ranges include i.
Let’s update index 13:
13 is 1101.1 to the last set bit, which gives us 14 (1110), and the range covered by index 14 is [14, 14].1 again, which gives us 16 (10000), and the range covered by index 16 is [1, 16].So, when updating index 13, we propagate the update to indices 14 and 16 because the ranges for these indices include 13.
void update(int i, int x, int bit[], int n) {
while (i <= n) {
bit[i] += x; // Update the value at index i
i += i & (-i); // Move to the next index whose range includes i
}
}
bit[13] = 5, bit[14] = 7, and bit[16] = 20.
We want to add 3 to index 13.
After the update, the array is:
bit[13] = 8, bit[14] = 10, and bit[16] = 23.
int sum(int i, int bit[]) {
int ans = 0;
while (i > 0) {
ans += bit[i]; // Add the value at index i
i -= i & (-i); // Move to the parent index
}
return ans;
}
Example of Sum Operation:
Let’s say we want to compute the sum up to index 13:
• Start at bit[13]: sum = 8.
• Move to bit[12]: sum = 8 + 9 = 17.
• Move to bit[8]: sum = 17 + 15 = 32.
So, the sum of elements from index 1 to 13 is 32.
Summary
• Finding the Rightmost Set Bit: You can isolate the rightmost set bit in a binary number using the operation x & -x.
• Removing the Rightmost Set Bit: You can remove the rightmost set bit by performing x = x - (x & -x).
• Fenwick Tree: Each index in a Fenwick Tree stores the sum of a specific range of elements, determined by the rightmost set bit of the index.
• The update operation propagates the update to all subsequent indices whose ranges include the updated index.
• The sum operation computes the prefix sum by moving up the tree from the current index to its ancestors.
By efficiently handling updates and queries, Fenwick Trees provide a powerful way to work with range sums in logarithmic time.
#include <bits/stdc++.h>
using namespace std;
class FenWickTree
{
public:
vector<int> BITree;
int n;
FenWickTree(vector<int> &arr)
{
n = arr.size();
BITree = vector<int>(n + 1, 0);
for (int i = 0; i < n; i++)
{
update(i + 1, arr[i]);
}
}
void update(int index, int value)
{
for (int i = index; i <= n; i += (i & -i))
{
BITree[i] += value;
}
}
int sum(int index)
{
int ans = 0;
for (int i = index; i > 0; i -= (i & -i))
{
ans += BITree[i];
}
return ans;
}
};
signed main()
{
vector<int> arr = {1, 2, 3, 4, 5, 6, 7};
FenWickTree ft(arr);
cout << ft.sum(3) << endl;
ft.update(3, 6);
cout << ft.sum(3) << endl;
// Range Sum Query at l=2 and r=5
cout << ft.sum(6+1) - ft.sum(2) << endl;
return 0;
}
class NumArray {
public:
vector<int> BITree;
vector<int> temp;
int n;
NumArray(vector<int>& nums) {
n = nums.size();
temp = nums;
BITree.resize(n + 1,0);
for (int i = 1; i <= n; i++) {
initialUpdate(i, temp[i - 1]);
}
}
void initialUpdate(int index, int val) {
for (int i = index; i <= n; i += (i & -i)) {
BITree[i] += val;
}
}
void update(int index, int val) {
int toDecrease=temp[index];
temp[index]=val;
for (int i = index+1; i <= n; i += (i & -i)) {
BITree[i] -= toDecrease;
BITree[i] += val;
}
}
int sumRange(int left, int right) { return sum(right+1) - sum(left); }
int sum(int index) {
int ans = 0;
for (int i = index; i > 0; i -= (i & -i)) {
ans += BITree[i];
}
return ans;
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* obj->update(index,val);
* int param_2 = obj->sumRange(left,right);
*/