MohammadParsaElahimanesh's blog

Can we find each Required node in segment tree in O(1)?
By MohammadParsaElahimanesh, history, 4 years ago, In English

Hello, Can we find for example each red node (in picture blow) in O(1)?

I try hard to find a way such as binary operations to get my ans. but i can't :(

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Yes, somewhat, if N is a power of two. It's quite difficult to explain, so I'll show it for example with n=16 for query [2;10] in zero numeration (as in your picture).

Let l and r be the left and right bounds (inclusive) of the query, from 0 to N-1. Then the most significant set bit of l ^ r shows you where the query gets divided for the first time. Then you can split your query into two queries: l..m-1 and m..r. Example: l ^ r = 8. The highest bit is 3, which means the query splits at level 3 counting from bottom, i.e. at the first level. After that the query is split to 2..7 and 8..10, m=8.

Then you can check the least significant set bit of l to find the level of the most left red node. Example: l=2, the lowest bit is 1, so 1 row from bottom. It can then be shown that all red nodes for query l..m-1 are returned by the following simple iterative algorithm: start with v equal to this this red node, return v, then set v=(v+1)/2 (assuming nodes are numbered top-bottom then left to right, with the root being 1). Repeat until you reach the end of the query. In other words, we take the first red node, then the parent of its right neighbour, then the parent of its right neighbour, etc. Example: l=2, m=7, we start with node [2;3] with ID 9. Then we switch to node with ID (9+1)/2=5, i.e. [4;7]. It's the last red node for this query because its right bound is exactly m-1.

Do the same for the right query (m..r), except checking the least significant unset bit of r, and using iterative formula v=v/2-1. Example: r=10, the least unset bit is 0, so we start with the node at the very bottom for range [10;10] with ID 26. Then switch to node 26/2-1=12, i.e. [8;9]. Its left bound is exactly m so we stop here.

Surely this does not look like a $$$\mathcal{O}(1)$$$ algorithm because of the iterative formula, but it's a very simple loop with absolutely no conditions, and the indexes can be evaluated in parallel, so if you have AVX, or even better AVX2 with gather-scatter, you may be able to make the fastest segment tree in the world!

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

Yes, this is possible. Take a look at the code in the Efficient and easy segment trees blog post: to get the half-open interval $$$[l,r)$$$, run

  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) f(tree[l++]);
    if (r&1) f(tree[--r]);
  }

This isn't strictly speaking $$$O(1)$$$ per vertex because of the if (l&1) condition, but you can easily make it $$$O(1)$$$ per vertex by using __builtin_ctz to skip to the next iteration that satisfies the condition.

My segment tree code is all based around this bottom-up/iterative traversal: https://github.com/ecnerwala/cp-book/blob/master/src/seg_tree.hpp

→ Reply