Skip to content

Instantly share code, notes, and snippets.

@coderek
Created October 20, 2017 20:54
Show Gist options
  • Save coderek/9b70d401d900e6681ee304e75b84dff3 to your computer and use it in GitHub Desktop.
Save coderek/9b70d401d900e6681ee304e75b84dff3 to your computer and use it in GitHub Desktop.
function segment(list) {
const nodes = [];
for (let i=0;i<list.length;i++) {
nodes.push({max: [list[i], i], range: [i, i+1]});
}
let l = list.length;
while (l > 0) {
for (let i=0;i<l-1;i+=2) {
let maxIdx = nodes[i]['max'];
if (nodes[i+1]['max'] > maxIdx) {
maxIdx = nodes[i+1]['max'];
}
nodes[i/2] = {
max: maxIdx,
range: [nodes[i]['range'][0], nodes[i+1]['range'][1]],
left: nodes[i],
right: nodes[i+1]
};
}
if (l % 2 != 0) {
nodes[(l-1)/2] = nodes[l-1];
}
l /= 2;
}
return nodes[0];
}
function query(s, e, segment) {
if (s >= e) return [0,-1];
const { range, max, left, right } = segment;
if ( s == range[0] && e == range[1]) {
return max;
}
let leftMax = [0,-1], rightMax = [0,-1];
if ( left ) {
const leftStart = Math.max(s, left.range[0]);
const leftEnd = left.range[1];
leftMax = query(leftStart, leftEnd, left);
}
if ( right ) {
const rightStart = right.range[0];
const rightEnd = Math.min(right.range[1], e);
rightMax = query(rightStart, rightEnd, right);
}
if (leftMax > rightMax) {
return leftMax;
} else {
return rightMax;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment