Can someone help me with this [problem][1] on segment trees. Here is my
[2]. I am applying binary search on a sum segment tree to find the break point where my sum first time becomes k. It is sort of lower_bound method. I am getting TLE in test case 9 rest all are AC. Also can someone suggest some good questions on segment trees to practice. I am a beginner here :)
[1]: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/k-th-bit-faae0e0d/
[2]: https://ideone.com/8T2Sns
In your implementation you are using the segment tree as a black box to perform sum over ranges of the form [0..x]. So your binary search takes \mathcal{O}(\log n) and each segment tree query also takes \mathcal{O}(\log n) which is why you get a complexity of \mathcal{O}(\log ^2 n) per query of type 2.
You can do better than this by modifying the segment tree query to your advantage. The aim is to get the first index i such that \sum A[0..i] = K. Every segment tree node stores a sum over some range. Suppose node u covers A[u_L..u_R], the sum of this subarray is stored as \text{tree}_u, and u_M = \lfloor(u_L + u_R)/2\rfloor. Assume you are required to find the first index i such that \sum A[u_L..i] \ge k. This is just a general version of the problem at hand.
Now if \sum A[u_L..u_M] \ge k, this means that and i lies in [u_L..u_M]. But \sum A[u_L..u_M] is just \text{tree} _ {\text{left_child}(u)}, so we already have that! Conversely, if \text{tree} _ {\text{left_child}(u)} < k, i lies in [u_M+1..u_R].
Let f(u, k) denote this index i, then f can be recursively defined as
Using this you can travel down the tree and end up at the exact index you need, so it reduces to \mathcal{O}(\log n) per query. Note that the case when answer is -1 is not covered here. If you understood the reasoning, you should be able to implement it without much difficulty.