Hello Everyone,
Learned some hard problem solving technique using Binary Index Tree(BIT) , wanted to share . Feel free to point any mistake and add more problems to this thread.
Pre-requiste
You can learn about BIT from wikipedia or these resource
You should also be aware of how to do combination of range update and point queries(check wikipedia) or
https://leetcode.com/discuss/general-discussion/1093346/introduction-to-fenwick-treebinary-indexed-treebit
In Short
-
Each cell in BIT is responsible for some range, how to find these range ?
Represent the number in 2 power for example 10 = 2^3 + 2^1
Take the right most as length and rest all start index(if there is nothing take 0) so for here it would [8, 9] why 9 because starting at 8 , next 2 elemenet would length is 2 and 8+2-1 =9.
Lets do this exercise for 11 = 2^3 + 2^1 + 2^0 right most is 1 so length is 1 and rest all is 10
So BIT index 11 store [10, 10]
Note that BIT is 1-index ,if you are asked to find any query in 0 ibndex, do a +1 and convert to 1 index.2nd important property is we can get the parent from any cell by clearing off right most MSB
For example 11 = 1011 in binary , so we take BIT[11] + BIT[10] + BIT[8]
BIT[11] give sum from [10,10]
BIT[10] give sum from [8, 9]
BIT[8] gives sum from [0, 7] and hence we have complete sum from [0, 10]
Warm-up Problems:
After reading about basic of BIT, you must solve these 2 problems to get hands dirty on BIT.
Solving these gives confidence in BIT and they are easy but important problems.
Make sure to use long long.
SPOJ : FENTREE, UPDATEIT
1375: Number of Times Binary String Is Prefix-Aligned
Hard Problems:
Real fun starts here.
- Fisrt familirize with what is lower_bound & upper_bound.
1.lower_bound first iterator of value >=
2.upper_bound return value >
- in case in lower_bound you need last index <= (GFG problem requires that) just do upper_bound -1. in this diagram you get index 6 then.
- If the element doesnt exist in search , both lower bound and upper bound return same result.
- Whether to iterate from begining or end of vector.
Mostly you iterate from begining unless problem ( like LC 315) asked something specific.
Template:
- Copy the input vector into another vector and sort it. Why we need another sorted vector is an important concept to understand here since this is used in all problem.
Basically in Step 4 we iterate the input array (not the sorted array) and we find its position in sorted array and then see how many element before or after (depend on problem)
occured and then sum it up. Will explain in detail in the problem. - Setup BIT array of 1+n , where n is array size.
- Iterate from begin/ end.
- See what the problme is asking for and acording use lower/upper bound We want everything less than current
- Update the frequency of this current element in BIT array.
Lets see this template working in this problem.
LC 315: Smaller Number than Self
Step 1 & 2 is standard.
Step 3 : This question asked every element smaller on its right side, so start from end.
Step 4: Problem is asking for less than current element so lower_bound is needed.
Since BIT works on 1 index, increment index by 1.
Now we want everything less than current value so sum(index -1).
Step 5: Increment index by 1.
Step 4 & 5 in detail
A = [5,2,6,1]
Sorted_A = [1, 2, 5, 6]
BIT = [0, 0, 0, 0, 0]
loop from end
i = 3
nums[i] = 1
its position in Sorted_A is 0 (lower_bound of 1 is 1 itself)
BIT works on 1 index so index is 1.
now we want everything less than 1 so sum(0) which gives 0 and we know nothing is less than 1 on right side so res[3] = 0
update idx=1 in BIT array , we are trying to communicate to all higher index that a smaller number (1) is available.
This is a key part to understand which direction to update and which direction to sum, if you see 493 the process(sum and update) is exact reverse.
so BIT = [0, 1, 1, 0, 1] (1st , 2nd and 4th index is incremented by 1)
i=2
nums[i] = 6
position in sorted_A is 3
+1 for BIT index = 4
we want all less than this index so sum(3)
now since 1 occured in previous iteration and it has updated BIT array so sum(3) gives 1, res[2] = 1
after update(4) we get BIT = [0, 1, 1, 0, 2]
class Solution {
vector<int> BIT;
int sum (int idx){
int ret =0;
for(; idx > 0; idx -= (idx & -idx))
ret += BIT[idx];
return ret;
}
void update(int idx){
for(; idx < BIT.size(); idx += (idx & -idx))
BIT[idx]++;
}
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end()); // Step 1
BIT.resize(1+n); // Step 2
vector<int> ans(nums.size());
for(int i =n-1; i>=0; --i){
int idx = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin();
++idx;// since BIT starts with 1
ans[i] = sum(idx-1);
update(idx);
}
return ans;
}
};Approach :
- When a bulb is lighted , we can find the left most and right most index which idx - left -1 and idx + right+ 1, respectively. First they should be valid boundary i.e. [1,n] , and also they should be lighted as per problem statement.
- We do a BIT sum of this index.
- Next we do a BIT sum of left, right and see if right - sum ==1 or sum - left ==1
- Why this works: because everytime we are lighting a bulb we are telling(BIT update) every one to the right of this index.
- Why we check difference of 1 , because if at left index 'm' bulbs are lighted and then at current index m+1 are lighted , that means all the ones which are between this range are off still.
class Solution {
vector<int> BIT;
void update(int i){
while( i < BIT.size()){
BIT[i]++;
i += ( i & -i);
}
}
int sum(int i){
int ret =0;
while(i > 0 ){
ret += BIT[i];
i -= ( i & -i);
}
return ret;
}
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int n = bulbs.size();
BIT.resize(1+n, 0);
vector<bool> visited(1+n, false);
for(int i =0; i < n ; ++i){
int idx = bulbs[i];
update(idx);
int left = idx - k -1;
int right = idx + k +1;
int mysum = sum(idx);
visited[idx] = true;
if(
(left > 0 and visited[left] and mysum - sum(left)==1)
or
(right <=n and visited[right] and sum(right) - mysum==1)
)
return i+1;
}
return -1;
}
};LC 493: Reverse Pair
Exactly same as above but one key difference
Here if we get smaller number , we need to get the count of all the bigger number (2 * x - 1 ) appeared in past iteration .
Now since the smaller number index would be smaller, all the bigger number has to tell to the left of it . that means update should happen toward left.
class Solution {
int n;
vector<int> BIT;
int sum(int i){
int ret = 0;
for(; i < BIT.size(); i += (i & -i))
ret += BIT[i];
return ret;
}
void update(int i){
for(; i >0; i -= (i & -i))
BIT[i]++;
}
public:
int reversePairs(vector<int>& nums) {
n = nums.size();
BIT.resize(1+n);
vector<int> sorted_nums(nums);
sort(sorted_nums.begin(), sorted_nums.end());
int ans = 0;
for(int i =0; i < n; ++i){
int idx = lower_bound(sorted_nums.begin(), sorted_nums.end() , (long)2*nums[i] + 1) - sorted_nums.begin();
++idx;
ans += sum(idx);
idx = lower_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]) - sorted_nums.begin();
++idx;
update(idx);
}
return ans;
}
};Try solving this problem too, same as above, except lower/upper bound difference.
SPOJ : INVCNT
BIT using Prefix Sum
Key difference is instead of number , we are asked sub-array whose sum lies in certain range.
Basically the problem involved sub-array instead of array element.
When problem asked for subarray sums, one standard approach come to mind is prefix sum.
- Generate prefix sum
- Generate sorted prefix_sum
These two will replace the nums & sorted_nums in template.
Also assign a unique rank or number to each of the psum, why are we doing it, because we are using this unique number to update the BIT.
remember that psum can be -ve and BIT works on +ve indices
you have 2 option , - either make all the psum +ve
- or assign a unique rank to each psum and then use this unique rank to update BIT.
For more details I added another post https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/1547068/binary-index-tree-in-2-different-ways
[-2,5,-1], lower = -2, upper = 2
Suppose psum[i] is 7 , we are looking if any previous psum lies in range [5, 9]
which means [psum[i]-upper , psum[i]-lower]
so look for this psum in sorted_psum and then do the sum(higher)-sum(lower)
finally update(rank(psum[i])) ; remember we are dealing BIT index on rank of psum not the psum itself as psum cna be -ve.
class Solution {
vector<int> BIT;
int n;
void update(int i){
for(; i < BIT.size(); i += (i & -i))
BIT[i]++;
}
int sum(int i){
int ret =0;
for(; i > 0; i -= (i& -i))
ret += BIT[i];
return ret;
}
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
n = nums.size();
vector<long> psum(1+n, 0);
for(int i =0; i <n; ++i)
psum[i+1] = psum[i] + nums[i];
vector<long> sorted_psum(psum);
sort(sorted_psum.begin(), sorted_psum.end());
// Give a unique id to each psum
unordered_map<int, int> rank;
for(int i =0; i <= n ; ++i)
rank[sorted_psum[i]] = 1+i;
BIT.resize(2+n, 0);// WHy 2 because 1 for BIT index starts with 1 index
// 2nd one is because our psum array has a 0 sum also
// Why we added 0 because psum -lower or upper could be 0.
int ans =0;
for(int i =0; i <= n ; ++i){
long up = psum[i] - lower;
long lo = psum[i] - upper;
// Now check in sorted psum array
int lower_idx = lower_bound(sorted_psum.begin(), sorted_psum.end(), lo)-sorted_psum.begin();
int higher_idx = upper_bound(sorted_psum.begin(), sorted_psum.end(), up)-sorted_psum.begin();
ans += sum(higher_idx) - sum (lower_idx);
update(rank[psum[i]]);
}
return ans;
}
};GFG Count of substrings in a Binary String that contains more 1s than 0s or
2031 Count Subarrays With More Ones Than Zeros
The page suggest using merge sort but I did using BIT with same time complexity. Try BIT way.
It is almost similar to above problem.
Will add more problem to this list.
End Note:
- Make sure you can now write bug free update and sum routine , its fairly easy after some practice.
- Notice what problem is asking and apply the template.
- If problem involved prefix sum, use rank method and use that array instead.
- Think where to start iterarting from.
- lower_bound/upper_bound what to use
- In general, it problem is asking for some kind of count in array ranges, think if BIT can be applied in some way.