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:
Update value at a given position
Compute prefix sum of A upto i, i ≤ n
Search for a prefix sum (something like a
lower_bound
in the prefix sum array of A)
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. The only issue with this is that binary search in a BIT has time complexity of O(log2(N)) (other operations can be done in O(log(N))). Even though this is naive,
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 complexity due to which they be even slower than O(log2(N)) of BIT.
Hence we need an efficient searching method in BIT itself.