Iterative Segment Tree
Here is what the structure looks like for :
The blue nodes shown are those which are relevant to the query . Also note that some nodes, in this case and , will never be accessed. In particular:
- If a node has an odd index and its corresponding range can be doubled to the left, its parent will represent that doubled range.
- If a node has an even index and its corresponding range can be doubled to the right, its parent will represent that doubled range.
- Otherwise, is useless.
For instance, node corresponds to the range , which cannot be doubled to the left as it would result in the range . Therefore, its parent, node , is useless.
Similarly, node corresponds to the range which also cannot be doubled to the right as it would result in the range , which is out of bounds of our array.
Walking
Consider the following problem: given a range and a predicate , find the smallest such that
where is either 0 or 1 and also monotonically increasing in . If no such exists, return .
Consider the following algorithm:
- Initialize . This is the accumulator for our partial product.
- Let . While is a left child and its parent’s range does not contain , set to its parent.
- If , where denotes the accumulation of ‘s range , set .
- Otherwise, set .
- If , return . Otherwise, repeat from step 2.
Note that step 2 can be done in time by the following snippet:
int u = l + n, x = __lg(min(u & -u, r - l));
u >>= x;Therefore, the overall runtime of this algorithm is .
Here is a clean implementation.