### rohit_1801's blog

By rohit_1801, history, 6 weeks ago,

Hello Community, I wanted to have a function to find order of key for an ordered set in java. As far as I know there is no any predefined function to find the number of elements lesser than the given element in an ordered set(treeset) in java in log(n) time? Can some one share their implementation. Thanks !!

• 0

 » 6 weeks ago, # |   0 You can refer to these blogs: 1, 2, 3Also, I made a class PBDS_Compressed, which can take values in a fixed range, implemented using the idea of a Segment Tree (I've not used it much, but I don't think there is any problem in the implementation). Codeclass PBDS_Compressed { int[] tree; int n; public PBDS_Compressed(int n) { this.n = powerOf2(n); this.tree = new int[2 * this.n]; } private static int powerOf2(int n) { if ((n & (n - 1)) == 0) return n; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; return n + 1; } public int size() { return n; } public void insert(int key) { if (key < 0 || key >= n) throw new IndexOutOfBoundsException(key + " should be between 0 and " + (n - 1) + " (both inclusive)."); insert(1, 0, n - 1, key); } // Only in range [0, n) private void insert(int v, int l, int r, int key) { if (key < l || key > r) return; if (l == r) { tree[v]++; return; } int m = (l + r) >> 1, left = v << 1, right = left + 1; insert(2 * v, l, m, key); insert(2 * v + 1, m + 1, r, key); tree[v] = tree[left] + tree[right]; } public int orderOfKey(int key) { if (key <= 0) return 0; key = Math.min(key, n); return orderOfKey(1, 0, n - 1, 0, key - 1); } // The number of elements that are strictly smaller than the key private int orderOfKey(int v, int l, int r, int ql, int qr) { if (ql > r || qr < l) return 0; if (ql <= l && qr >= r) return tree[v]; int m = (l + r) >> 1; return orderOfKey(2 * v, l, m, ql, qr) + orderOfKey(2 * v + 1, m + 1, r, ql, qr); } public int findByOrder(int i) { if (i < 0 || i >= tree[1]) throw new IndexOutOfBoundsException("Currently " + tree[1] + " elements in the tree. Asked index " + i + "."); return findByOrder(i, 1, 0, n - 1); } // The i-th largest element private int findByOrder(int i, int v, int l, int r) { if (l == r) return v - n; int m = (l + r) >> 1, left = v << 1, right = left + 1; if (tree[left] <= i) return findByOrder(i, left, l, m); return findByOrder(i - tree[left], right, m + 1, r); } } 
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for your reply. The only problem i face with your code is that it limits me to add values in the range [0,n) . I had the constraints for n<=1e5 and for arr[i]<=1e9. So do you have any other template for this? Basically i want to use this in this leetcode problem : https://leetcode.com/contest/weekly-contest-387/problems/distribute-elements-into-two-arrays-ii/
•  » » » 6 weeks ago, # ^ |   0 This is why there is compressed in the name. In case our range is large, we have to do coordinate compression.Also that problem can be solved using Fenwick Tree (as mentioned in the 1st blog).