**NOTE** : Knowledge of Binary Indexed Trees is a prerequisite.↵
↵
## Problem Statement↵
↵
Assume we need to solve the following problem. We have an array, $A$ of length $N$ with only non-negative values. We want to perform the following operations on this array:↵
↵
1. Update value at a given position↵
↵
2. Compute prefix sum of $A$ upto $i, i \leq N$↵
↵
3. Search for a prefix sum (something like a `lower_bound` in the prefix sums array of $A$)↵
↵
<br>↵
↵
## Basic Solution↵
↵
Seeing such a problem we might think of using a Binary Indexed Tree (BIT) and implementing a binary search for type $3$ operation. Its easy to see that binary search is possible here because prefix sums array is monotonic (only non-negative values in $A$).↵
↵
The only issue with this is that binary search in a BIT has time complexity of $O(log^2(N))$ (other operations can be done in $O(log(N))$). Even though this is naive, here is how to do it:↵
↵
<spoiler summary="Implementation">↵
`int sum(pos)` -> computes prefix sum upto `pos` in BIT in $O(log(N))$↵
↵
~~~~~↵
int binary_search(int v) // v is the value we are searching↵
{↵
int l = 1, r = N;↵
while(l != r)↵
{↵
int mid = (l+r) / 2;↵
if(sum(mid) < v)↵
l = mid+1;↵
else↵
r = mid;↵
}↵
return l;↵
}↵
~~~~~↵
↵
$O(log(N))$ iteration in `binary_search`, each iteration computes `sum(pos)` once.<br>↵
Time Complexity : $O(log(N)) * O(log(N)) = O(log^2(N))$↵
</spoiler>↵
↵
Most of the times this would be fast enough (because of small constant of above technique). But if the time limit is very tight, we will need something faster. Also we must note that there are other techniques like segment trees, policy based data structures, treaps, etc. which can perform operation $3$ in $O(log(N))$. But they are harder to implement and have a high constant factor associated with their time complexities due to which they might be even slower than $O(log^2(N))$ of BIT.↵
↵
Hence we need an efficient searching method in BIT itself.↵
↵
<br>↵
↵
## Efficient Solution↵
↵
We will make use of **binary lifting** to achieve $O(log(N))$ (well I actually do not know if this technique has a name but I am calling it binary lifting because the algorithm is similar to binary lifting in trees using sparse table).↵
↵
#### What is binary lifting?↵
↵
In binary lifting, a value is increased (or lifted) by powers of $2$, starting with the highest possible power of $2$, $2^{ceil(log(N))}$, down to the lowest power, $2^0$.↵
↵
#### How binary lifting is used?↵
↵
Assume `pos` is position of lower bound of `v` in prefix sums array, where `v` is the value we are searching for. So, we set each bit of `pos`, from most significant bit to least significant bit. Whenever a bit is set to $1$, the value of `pos` increases (or lifts). While increasing or lifting `pos`, we make sure that prefix sum till `pos` should be less than `v`, for which we maintain the prefix `sum` and update it whenever we increase or lift `pos`. See implementation.↵
↵
The correctness is not very difficult to prove and I am leaving it as an exercise for the readers (Apologies for my laziness :P)**More insight:**<br>↵
We are going from $log(N)$th to $0$th bit, since we only need $log(N)$ bits for all possible values of `pos`. Now, lets assume we are trying to determine the value of $i$th bit. First we check if setting the $i$th bit won't make `pos` greater than $N$, which is size of the array. Then we check that if we lift `pos` to the new position, then the value of sum should be less than `v`, the value we are searching for. If this condition is true, then target position lies above the `pos + 2^i`, but below `pos + 2^(i+1)`. This is because if target position was above `pos + 2^(i+1)`, then `pos` would have been already lifted by $2^{i+1}$ (this logic is similar to binary lifting in trees). If it is false, then target value lies between `pos` and `pos + 2^i`, so we try to lift by a lower power of 2. It is easy to see that we will reach $1$ less than our target position eventually, since `sum < v` always.↵
↵
It is not very difficult to come up with a rigorous proof of correctness and I am leaving it as an exercise for the readers.<br>↵
**HINT** : Each position in `bit` stores sum of a power of 2 elements, sum of last $i & -i$ elements till $i$ are stored at position $i$ in `bit`. I hope this will atleast help you think of an intuitive proof.↵
↵
#### Implementation :↵
↵
~~~~~↵
// This is equivalent to calculating lower_bound on prefix sums array↵
// LOGN = log(N)↵
↵
int bit[N]; // BIT array↵
↵
int bit_search(int v)↵
{↵
int sum = 0;↵
int pos = 0;↵
↵
for(int i=LOGN; i>=0; i--)↵
{↵
if(pos + (1 << i) < N and sum + bit[pos + (1 << i)] < v)↵
{↵
sum += bit[pos + (1 << i)];↵
pos += (1 << i);↵
}↵
}↵
↵
return pos + 1; // +1 because 'pos' will have position of largest value less than 'v'↵
}↵
~~~~~↵
↵
#### Taking this forward↵
↵
You must have noted that proof of correctness of this approach relies on the property of the prefix sums array that it **monotonic**. This means that this approach can be used for with any operation that maintains the monotonicity of the prefix array, like multiplication of positive numbers, etc.↵
↵
Thats all folks!↵
↵
**PS** :I will try to come up with a formal proof and update this blog as soon as possible. Please let me know if there are any mistakes.
↵
## Problem Statement↵
↵
Assume we need to solve the following problem. We have an array, $A$ of length $N$ with only non-negative values. We want to perform the following operations on this array:↵
↵
1. Update value at a given position↵
↵
2. Compute prefix sum of $A$ upto $i, i \leq N$↵
↵
3. Search for a prefix sum (something like a `lower_bound` in the prefix sums array of $A$)↵
↵
<br>↵
↵
## Basic Solution↵
↵
Seeing such a problem we might think of using a Binary Indexed Tree (BIT) and implementing a binary search for type $3$ operation. Its easy to see that binary search is possible here because prefix sums array is monotonic (only non-negative values in $A$).↵
↵
The only issue with this is that binary search in a BIT has time complexity of $O(log^2(N))$ (other operations can be done in $O(log(N))$). Even though this is naive, here is how to do it:↵
↵
<spoiler summary="Implementation">↵
`int sum(pos)` -> computes prefix sum upto `pos` in BIT in $O(log(N))$↵
↵
~~~~~↵
int binary_search(int v) // v is the value we are searching↵
{↵
int l = 1, r = N;↵
while(l != r)↵
{↵
int mid = (l+r) / 2;↵
if(sum(mid) < v)↵
l = mid+1;↵
else↵
r = mid;↵
}↵
return l;↵
}↵
~~~~~↵
↵
$O(log(N))$ iteration in `binary_search`, each iteration computes `sum(pos)` once.<br>↵
Time Complexity : $O(log(N)) * O(log(N)) = O(log^2(N))$↵
</spoiler>↵
↵
Most of the times this would be fast enough (because of small constant of above technique). But if the time limit is very tight, we will need something faster. Also we must note that there are other techniques like segment trees, policy based data structures, treaps, etc. which can perform operation $3$ in $O(log(N))$. But they are harder to implement and have a high constant factor associated with their time complexities due to which they might be even slower than $O(log^2(N))$ of BIT.↵
↵
Hence we need an efficient searching method in BIT itself.↵
↵
<br>↵
↵
## Efficient Solution↵
↵
We will make use of **binary lifting** to achieve $O(log(N))$ (well I actually do not know if this technique has a name but I am calling it binary lifting because the algorithm is similar to binary lifting in trees using sparse table).↵
↵
#### What is binary lifting?↵
↵
In binary lifting, a value is increased (or lifted) by powers of $2$, starting with the highest possible power of $2$, $2^{ceil(log(N))}$, down to the lowest power, $2^0$.↵
↵
#### How binary lifting is used?↵
↵
Assume `pos` is position of lower bound of `v` in prefix sums array, where `v` is the value we are searching for. So, we set each bit of `pos`, from most significant bit to least significant bit. Whenever a bit is set to $1$, the value of `pos` increases (or lifts). While increasing or lifting `pos`, we make sure that prefix sum till `pos` should be less than `v`, for which we maintain the prefix `sum` and update it whenever we increase or lift `pos`. See implementation.↵
↵
We are going from $log(N)$th to $0$th bit, since we only need $log(N)$ bits for all possible values of `pos`. Now, lets assume we are trying to determine the value of $i$th bit. First we check if setting the $i$th bit won't make `pos` greater than $N$, which is size of the array. Then we check that if we lift `pos` to the new position, then the value of sum should be less than `v`, the value we are searching for. If this condition is true, then target position lies above the `pos + 2^i`, but below `pos + 2^(i+1)`. This is because if target position was above `pos + 2^(i+1)`, then `pos` would have been already lifted by $2^{i+1}$ (this logic is similar to binary lifting in trees). If it is false, then target value lies between `pos` and `pos + 2^i`, so we try to lift by a lower power of 2. It is easy to see that we will reach $1$ less than our target position eventually, since `sum < v` always.↵
↵
It is not very difficult to come up with a rigorous proof of correctness and I am leaving it as an exercise for the readers.<br>↵
**HINT** : Each position in `bit` stores sum of a power of 2 elements, sum of last $i & -i$ elements till $i$ are stored at position $i$ in `bit`. I hope this will atleast help you think of an intuitive proof.↵
↵
#### Implementation :↵
↵
~~~~~↵
// This is equivalent to calculating lower_bound on prefix sums array↵
// LOGN = log(N)↵
↵
int bit[N]; // BIT array↵
↵
int bit_search(int v)↵
{↵
int sum = 0;↵
int pos = 0;↵
↵
for(int i=LOGN; i>=0; i--)↵
{↵
if(pos + (1 << i) < N and sum + bit[pos + (1 << i)] < v)↵
{↵
sum += bit[pos + (1 << i)];↵
pos += (1 << i);↵
}↵
}↵
↵
return pos + 1; // +1 because 'pos' will have position of largest value less than 'v'↵
}↵
~~~~~↵
↵
#### Taking this forward↵
↵
You must have noted that proof of correctness of this approach relies on the property of the prefix sums array that it **monotonic**. This means that this approach can be used for with any operation that maintains the monotonicity of the prefix array, like multiplication of positive numbers, etc.↵
↵
Thats all folks!↵
↵
**PS** :
