Algo Advance

Most Beautiful Item for Each Query You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively. You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0. Return an array answer of the same length as queries where answer[j] is the answer to the jth query. Constraints: 1 <= items.length, queries.length <= 10^5 items[i].length == 2 1 <= pricei, beautyi, queries[j] <= 10^9 Analysis: The first step can be to sort the items based on the price. Then we can narrow down the search range by a binary search. But the beauty is not sorted yet. So if without further treatment, we need to scan through the query range, the time complexity is O(N). The query length could be as large as 1e5, thus the overall time complexity is O(N*M) ~ 1e10, which is

Segment Tree - Question List Question 1:  Most Beautiful Item for Each Query More Questions Upper Layer

Segment tree can be viewed as an abstract data structure which using some more space to trade for speed. For example, for a typical question with O(N^2) time complexity, the segment tree method can decrease it to O(N*log(N)).  To make it understandable, let us consider one example. Say we have an integer array of N size, and what we want is to query the maximum with a query range [idx1, idx2], where idx1 is the left indexes, and idx2 is the right indexes inclusive. If we only do this kind of query once, then we just need to scan through the array from idx1 to idx2 once, and record the maximum, done. The time complexity is O(N), which is decent enough in most cases even though it is not the optimal one (for example, with a segment tree built, the time complexity can decrease down to O(log(N))). However, how about we need to query the array N times? If we continue to use the naïve way above, then the time complexity is O(N^2), since for each query we need to scan the query range once. We