Menu
I'm trying to solve this problem.
I found tutorial for this problem but I don't get how to build segment tree that will find amount of numbers less than x in O(log n) (x can change). In tutorial it has been omitted.
Can anyone explain me how to do it ?
985
The total number of nodes involved in the segment tree is 4*n. The total number of levels is log n and starting from one node at the first level, the number of nodes gets doubled at every level. So, total number of nodes = 1+2+4+8+.... +2^(log n) = 2^(logn + 1) -1 < 4n.
Size of the Array Used in Segment Tree Representation Thus, the size of the segment tree is (2 * n - 1), where n is the size of the input array. It is because the total number of leaf nodes will be s, and internal nodes will be n - 1. Therefore, n + n - 1 = 2 * n - 1 is the total size of the array.
Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2*n – 1.
Lazy propagation is a range update and query optimized implementation of a segment tree that performs both operation O(logN) time. *In short, as the name suggests, the algorithm works on laziness for what is not important at the time. Don't update a node until needed, which will avoid the repeated sharing.
It is pretty simple:
Store a sorted array of all numbers in a range covered by a particular node
( O(n * log n) memory and time for initialization).
To answer a query, decompose the query segment into O(log n) nodes(the same way as it is done for a standard min/max/sum segment tree) and run binary search over the array stored in each of those nodes to find the number of elements less than x. It gives O(log^2 n) time per query. You can also achieve O(log n) using fractional cascading, but it is not necessary.
59
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
