range_max.js

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;
    }
}