[Tutorial] Searching Binary Indexed Tree in O(log(N))

Правка en4, от sdnr1, 2018-08-21 10:48:16

NOTE : Knowledge of Binary Indexed Trees is a prerequisite.
(If you don't wanna read the entire blog, Binary Lifting is the answer :P)

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 ≤ n

  3. Search for a prefix sum (something like a lower_bound in the prefix sums 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. 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(log2(N)) (other operations can be done in O(log(N))). Even though this is naive,

Implementation

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 might be even slower than O(log2(N)) of BIT.

Hence we need an efficient searching method in BIT itself.


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 sparse tables).

Implementation :

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;
}
Теги #binary-lifting, #binary search, binary indexed tree, bit

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en19 Английский sdnr1 2018-08-22 15:35:12 132
en18 Английский sdnr1 2018-08-22 13:14:18 53
en17 Английский sdnr1 2018-08-22 13:12:08 114
en16 Английский sdnr1 2018-08-22 12:52:42 174
en15 Английский sdnr1 2018-08-22 12:50:46 390 (published)
en14 Английский sdnr1 2018-08-22 11:41:30 953 (saved to drafts)
en13 Английский MikeMirzayanov 2018-08-22 11:10:35 7
en12 Английский sdnr1 2018-08-22 11:05:32 20
en11 Английский sdnr1 2018-08-22 10:48:05 25 (published)
en10 Английский sdnr1 2018-08-22 10:46:44 36 (saved to drafts)
en9 Английский sdnr1 2018-08-21 22:37:35 39
en8 Английский sdnr1 2018-08-21 22:28:02 1056 Added some more insight for better understanding of the algorithm
en7 Английский sdnr1 2018-08-21 21:57:33 96
en6 Английский sdnr1 2018-08-21 21:25:18 988 (published)
en5 Английский sdnr1 2018-08-21 18:19:38 867
en4 Английский sdnr1 2018-08-21 10:48:16 321
en3 Английский sdnr1 2018-08-21 10:12:15 228
en2 Английский sdnr1 2018-08-21 10:07:53 214
en1 Английский sdnr1 2018-08-21 09:55:51 1869 Initial revision (saved to drafts)