Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Range in range (solution 2)
import data_structure.persistent.PersistentSegmentTree;
import java.util.Arrays;
import java.util.HashMap;
import java.util.TreeMap;
public class CountRangeCoveringRangeOnlinePersistent {
TreeMap<Integer,Integer> endMap;
PersistentSegmentTree segmentTree;
/**
* Prepare the online query.
*
* @cost O(nlogn) where n = ranges.length
*
* @warning Destroys the given target ranges array.
*
* @param ranges target ranges
*/
public CountRangeCoveringRangeOnlinePersistent(int[][] ranges) {
Arrays.sort(ranges, (a, b) -> a[1] - b[1]);
int n = ranges.length;
int maxRange = ranges[n-1][1];
segmentTree = new PersistentSegmentTree(maxRange, n);
int root = 1;
endMap = new TreeMap<>();
endMap.put(-1, 0);
for (int i = 0; i < n ;) {
int j = i;
int end = ranges[i][1];
while (j < n && ranges[j][1] == end) {
root = segmentTree.add(ranges[j][0], 1, root);
j++;
}
i = j;
endMap.put(end, root);
}
}
/**
* Counts how many ranges in [l,r).
*
* @COST O(logn) where n = ranges.length
*
* @param l start of the query range(inclusive)
* @param r end of the query range(exclusive)
* @return number of target ranges covered by [l,r)
*/
public int query(int l, int r) {
int targetRoot = endMap.floorEntry(r).getValue();
return segmentTree.sum(l, r, targetRoot);
}
}
/**
* Persistent segment tree (point add, range sum query)
*/
public class PersistentSegmentTree {
int N;
int M;
int[] seg;
int[] left;
int[] right;
int[] parent;
int newNodeId;
public PersistentSegmentTree(int N, int Q) {
N = Math.max(16, Integer.highestOneBit(N-1)<<2);
M = (N >> 1);
int level = level(N);
int qdata = Q * (level+1);
seg = new int[N+qdata];
left = new int[N+qdata];
right = new int[N+qdata];
parent = new int[N+qdata];
parent[1] = -1;
for (int x = 1 ; x < M ; x++) {
left[x] = x*2;
right[x] = x*2+1;
parent[left[x]] = x;
parent[right[x]] = x;
}
newNodeId = (M-1)*2+2;
}
public static int level(int m) {
return m == 0 ? 1 : level(m/2) + 1;
}
private int make(int oldId) {
parent[newNodeId] = parent[oldId];
left[newNodeId] = left[oldId];
right[newNodeId] = right[oldId];
seg[newNodeId] = seg[oldId];
return newNodeId++;
}
private int makeBottom(int oldId, int newValue) {
int newID = make(oldId);
seg[newID] = newValue;
return newID;
}
private int makeLeftChildParent(int oldParId, int newLeftChildID) {
int newID = make(oldParId);
left[newID] = newLeftChildID;
parent[newLeftChildID] = newID;
compute(newID);
return newID;
}
private int makeRightChildParent(int oldParId, int newRightChildID) {
int newID = make(oldParId);
right[newID] = newRightChildID;
parent[newRightChildID] = newID;
compute(newID);
return newID;
}
private void compute(int i) {
seg[i] = seg[left[i]] + seg[right[i]];
}
private boolean isLeftChild(int par, int child) {
return left[par] == child;
}
/**
* Updates value at position idx, at time root.
* Returns new root node index.
*
* @param idx
* @param value
*/
public int add(int idx, int value, int root) {
int[] seq = find(idx, root);
int oldNodeID = seq[--seqID];
int newValue = seg[oldNodeID] + value;
int i = makeBottom(oldNodeID, newValue);
int oldI = oldNodeID;
while (true) {
int par = seq[--seqID];
if (isLeftChild(par, oldI)) {
i = makeLeftChildParent(par, i);
} else {
i = makeRightChildParent(par, i);
}
oldI = par;
if (parent[i] == -1) {
return i;
}
}
}
public int seqID;
public int[] sequenceFromRoot = new int[32];
public int[] find(int pos, int root) {
int fr = 0;
int to = M;
int idx = root;
seqID = 0;
while (to - fr > 1) {
sequenceFromRoot[seqID++] = idx;
int med = (to + fr) / 2;
if (pos < med) {
idx = left[idx];
to = med;
} else {
idx = right[idx];
fr = med;
}
}
sequenceFromRoot[seqID++] = idx;
return sequenceFromRoot;
}
/**
* Finds minimum value from range [l,r).
*
* @param l
* @param r
* @return minimum value
*/
public int sum(int l, int r, int root) {
return sum(l, r, root, 0, M);
}
private int sum(int l, int r, int idx, int fr, int to) {
if (to <= l || r <= fr) {
return 0;
}
if (l <= fr && to <= r) {
return seg[idx];
}
int med = (fr+to) / 2;
return sum(l, r, left[idx], fr, med) + sum(l, r, right[idx], med, to);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment