×

# Need help with a point update and range query question

 0 Given an array of 'N' integers, I need to perform two kinds of queries : Point update : U P : Arr[u] = P Given a L,R,P I need to find the smallest number in the range [L,R] that is greater than P. There are 'Q' queries. This question was in a Hiring challenge on Hackerearth (Challenge is over now) so I can't provide a link to the statement. I want to know if this problem can be solved with complexity better than Q*Log^2N asked 07 Jan, 23:57 1.3k●9 accept rate: 26% 2 https://discuss.codechef.com/questions/120954/minimum-number-query/120958 (08 Jan, 10:18) Thanks, but I think that has the same complexity as my solution. (08 Jan, 12:01)

 1 I did it using merge sort tree but it's as expensive as your's solution. Did you solve the last combinatorics question? answered 08 Jan, 03:48 10●2 accept rate: 0% I used a set and map for duplicates in every node of a segment tree. Got TLE. Yeah, I solved the last question. (08 Jan, 11:59) @hemanth_1 can you please explain your approach you applied to the last question? The stars and bars method was not working for me. (08 Jan, 17:48) Let dp[i][j] be the number of ways to take 'j' items in the first 'i' boxes. Since the limit for each box is 'A' for the first 'P' boxes, if i <= P, then: dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+....+dp[i-1][j-A], because you can take 0 to 'A' items from the ith box, and the rest must come from the previous ones. For i>P you can take the summation based on 'B'. I calculated this upto 1000 items. Now, you need to count number of ways to get sum >= X, so I calculated all possible ways and subtracted the number of ways to get sum
 0 @hemanth_1 did you use merge sort tree? answered 22 Jan, 01:01 66●5 accept rate: 0% I used a segment tree, with a set and a map in every node (22 Jan, 14:14) How did you find answer to second query using this? (22 Jan, 15:41) You need to find the smallest number > P in [L,R]. Since there is a set in every node of the segment tree, you can use upper_bound to find the smallest number > P in the range for that node. Since every query will visit at most O(logN) nodes, you only need to do this those many times. Finally, you will return the minimum of all upper_bounds that you found in all the nodes that you checked. (24 Jan, 21:29)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,302
×760
×202
×131
×53