atlasworld's blog

By atlasworld, history, 3 years ago,

You , are given an array of n elements and q queries . Both n and q can range upto 10^5 , and 1<=a[i] <= 10^9.

how to find / count all the elements less than a given element in each query .

queries are in the form of l , r , x where x is number and l and r are starting and ending indices.

Example: index 1 based

a[] = {5 , 3 , 2 , 2 , 3 , 1 , 2 , 9 , 10 , 2 }

q1 = 5 9 5

ans = 3 { 3 , 1 , 2}

q2 = 1 4 2

ans = 2 {2 , 2 }

The problem gives a feel of segment tree , but how to solve it using ST ?

any idea.

• -19

 » 3 years ago, # |   0 I don't know about segment tree, but it can be solved with SQRT decomposition and Mo's algorithm.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 mo's algorithm ? how . can u explain . despotovski01
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -9 If you are not familiar with Mo's algorithm, there's a good tutorial on HackerEarth about it. Do coordinate compression on all possible values found in array or queries, so that the range of the values becomes [0, 2 * 105). Then, keep count array for the values and a decomposed version of the array, which has blocks. Those arrays will keep track of the count of values for your queries. To calculate the total value of items less than x, you'll need just steps, because there are at most blocks, and at most values to be included that are not in a block. Total complexity is Edit: now I noticed that you asked how to find those elements as well. Just modify the previous algorithm to store the elements in each block in some data structure that supports efficient add / remove operations. A linked list or a hash table would be a good choice, because linked lists support addition and deletion of elements to the head and tail in O(1).
 » 3 years ago, # |   +1 You can solve each query in (logN)^2 using merge sort tree.
•  » » 3 years ago, # ^ |   0 what is merge sort tree , i dont know .
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +1 in segment tree you have to keep a vector as a node element and each node of segment tree will have the sorted range of left and right sub tree. then you will have to query in L to R for that when you reach a segment that completely lies in the range you have to do a binary search for number of element less than x in that segment and like this you have to add the answers coming from all segmentsyou can have a look to this link : https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial
•  » » » » 3 years ago, # ^ |   0 hey , cool . can you provide me some links from where u studied Merge sort tree . the idea of segment tree + binary search is very intutive .
•  » » » » » 3 years ago, # ^ |   +1 You can read about many applications from this site :http://e-maxx.ru/algo/segment_tree
•  » » » » » » 3 years ago, # ^ |   0 Thanks very much .
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 you can also handle updates if you store a set or multiset(which are in policy-based data structures) in each node instead of storing a vector
•  » » » » » » » » 3 years ago, # ^ |   0 for updates what should we do ? because a set can't store duplicates , and in multiset if u try to update a val , all duplicates will be updates , what to do in this case ?
•  » » » » » » » » » 3 years ago, # ^ |   0 you will have to erase an element and insert an element for erasing a single element in multiset first you find that element which will return an iterator to that element then you erase that element and then you insert the element which you want to
•  » » » » » » » » » 3 years ago, # ^ |   0 ok , i understood .
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 You have to use set which are in policy based data structures because normal set don't tell you the index of the integer so out can't find the no of elements less than x just using binary search ie. upper_boundFor Policy based data structures: https://codeforces.com/blog/entry/11080
•  » » » » » » » » » 3 years ago, # ^ |   0 Nice Explanation
 » 3 years ago, # |   +13 this can be done with a wavelet-tree
•  » » 3 years ago, # ^ |   0 what is wavelet — tree ? i dont know . please give me the link to it
•  » » » 3 years ago, # ^ |   0
 » 3 years ago, # | ← Rev. 3 →   +3 i got this blog . can anyone tell why we need to sort the array and querie. why sorting will not affect our answer https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/
•  » » 3 years ago, # ^ |   0 When you sort the array you also maintain the indices of the values. The BIT at each index basically stores whether that element is "active" in the array (0 or 1). Then to process the next query l, r, x, you "activate" every unactivated i such that ai < x by performing a point increment at every such i. To do so you just iterate through the sorted array. The answer to the query is then simply the range sum on the BIT over [l, r].I think you're misunderstanding why the sorting is done. The sorting is necessary to perform the right updates for the next query. What makes you think it would affect the answer in any way?Also note that this solution is offline unlike some of the suggestions you got.
•  » » » 3 years ago, # ^ |   0 ok , thanks aryaman
 » 3 years ago, # |   0 Mo's algorithm + Fenwick tree
 » 3 years ago, # | ← Rev. 3 →   0 There exist a version of this problem with update query you can find it in Vietnamese-SPOJ It can be done using sqrt-decomposition + 2d BIT. The idea is to divide the sequence in to sqrt(N) blocks, and you maintain the numbers of value which is greater than a specific value by a BIT. You can find my implementation for it here
•  » » 3 years ago, # ^ |   0 sqrt. decomposition is hard for me . i can't come up with my own . i have to look at editorial
 » 3 years ago, # |   +20 I see that same question asked every week... You can always use google to find a solution for such standard problems.
•  » » 3 years ago, # ^ |   -18 the question may be same for you but not for me .
 » 3 years ago, # |   0 I'm not sure if it's possible to solve this with a Segment Tree. I know for a fact that you can solve it by compressing the coordinates and using a Persistent Segment Tree, however, it seems like an overkill to me. I'd use a Wavelet Tree to solve this problem.
 » 3 years ago, # |   0 you can solve it using segment tree + coordinate compression.first we will make coordinate compression because values of a[i] is large (10 ^ 9) , so we will have new idx for every number.after that we will build the segment tree where tree[node] = tree[node * 2] + tree[node * 2 + 1]after that we will make query as it's sum problem that will return number of elements <= new idx of current element
•  » » 23 months ago, # ^ |   0 Can you provide me some links related to it? Couldn't really find a good explanation. Or maybe a code with good comments. Thank you.
 » 12 months ago, # |   0 Below is the code for solving this using Segment Tree. I think the complexity for constructing the tree is $O(nlgn)$. I am not sure about the time complexity to answer each query. #include using namespace std; #define N 100005 #define pb push_back #define endl "\n" vectortree[4*N]; void build(int v, int tl,int tr, const vector&arr){ if(tl>tr)return; if(tl == tr){ tree[v].pb(arr[tl]); return; } int tmid = tl + (tr -tl)/2; build(2*v, tl, tmid, arr); build(2*v+1, tmid+1, tr, arr); int i = 0, j = 0; int sz1 = (int)tree[2*v].size(), sz2 = (int)tree[2*v+1].size(); while(itr || eded)return 0; if(st<=tl && tr<=ed){ int idx = upper_bound(tree[v].begin(), tree[v].end(), value) - tree[v].begin(); return idx; } int tmid = tl + (tr - tl)/2; return query(2*v, tl, tmid, st, ed, value) + query(2*v+1, tmid+1, tr, st, ed, value); } vectorsolve(const vector &A, const vector>queries) { int n = (int)A.size(); build(1, 0, n-1, A); vectorans; for(auto&it:queries){ int st = it[0], ed = it[1], x = it[2]; int idx = query(1, 0, n-1, st, ed, x); ans.push_back(idx); } return ans; } int main() { vectorarr = {5 , 3 , 2 , 2 , 3 , 1 , 2 , 9 , 10 , 2 }; vector>queries = {{ 5, 9, 5}, { 1, 4, 2}}; auto ans = solve(arr, queries); for(auto&it:ans)cout<