Cer's blog

Question about Binary Indexed Tree
By Cer, 11 years ago, In English

I'm trying to learn a new data structure called "Binary Indexed Tree" and I have read the tutorial on TopCoder, it was really good but I can't understand the main purpose of this data structure, and when do we have to use it ? If someone has a better tutorial, I would be thankful for him, and provide me with some problems to practice please .

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This structure is useful instead of segments tree. It doesn't have the power of segments tree (for example, it doesn't support very complex range updates and Range Minimal Query), but it's much easier to implement (one very easy for for each query), works times faster and requires two times less memory.

In its basic form, this structure supports 'add X to element' and 'get sum of the first X elements' queries. But it can be modified to support range update queries.

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It can also be used for queries "get minimum/maximum of first X elements" (with updates "set element A[i] to x", with the condition that x can't be more than the previous value of A[i]). That comes handy in many problems.

Some example problems for BIT:

  • (sum-BIT) counting inversions in a permutation of length N: going from the end of the permutation, we mark in the BIT the numbers we've seen so far, and can quickly find how many numbers we've seen are larger than the one we're looking at right now

  • (max-BIT) longest increasing subsequence: in the BIT, we store the length of the LIS ending with number k; when adding a number x, the length of its LIS is 1+max. length from all LIS ending with numbers less than x; sample problem: 341B - Bubble Sort Graph and code: 4433701

  • (hard, min-BIT) 342E - Xenia and Tree, I solved it by using heavy-light path decomposition and constructing a BIT above every path; for every query, I iterate over all paths from the vertex to the root and update / compute the answer basically in the same way; in every BIT are stored the minima of (shortest distance downwards, out of the path, from this vertex minus distance from one end of the path) and to get the actual distance from some node, the distance of that node from the same end of the path must be added... code: 4450013

→ Reply