function buildSegmentTree(inputArray, nodeIndex, left, right, segmentTree) {
    // Current index: 0
    if (left === right) {
        segmentTree[nodeIndex] = inputArray[left];
    } else {
        let mid = Math.floor((left + right) / 2);
        buildSegmentTree(inputArray, nodeIndex * 2, left, mid, segmentTree);
        buildSegmentTree(inputArray, nodeIndex * 2 + 1, mid + 1, right, segmentTree);
        segmentTree[nodeIndex] = segmentTree[nodeIndex * 2] + segmentTree[nodeIndex * 2 + 1];
    }
}  
                    

function querySegmentTree(nodeIndex, left, right, queryLeft, queryRight, segmentTree) {
    // Current index: 0
    if (queryLeft > right || queryRight < left) {
        return 0;
    }
    if (queryLeft <= left && queryRight >= right) {
        return segmentTree[nodeIndex];
    }
    
    let mid = Math.floor((left + right) / 2);
    let leftSum = querySegmentTree(nodeIndex * 2, left, mid, queryLeft, queryRight, segmentTree);
    let rightSum = querySegmentTree(nodeIndex * 2 + 1, mid + 1, right, queryLeft, queryRight, segmentTree);
    
    return leftSum + rightSum;

}

Lekérdezés

function updateSegmentTree(index, newValue, nodeIndex, left, right, segmentTree) {
    // Current index: 0
    if (left === right) {
        segmentTree[nodeIndex] = newValue;
    } else {
        let mid = Math.floor((left + right) / 2);
        if (index <= mid) {
            updateSegmentTree(index, newValue, nodeIndex * 2, left, mid, segmentTree);
        } else {
            updateSegmentTree(index, newValue, nodeIndex * 2 + 1, mid + 1, right, segmentTree);
        }
        segmentTree[nodeIndex] = segmentTree[nodeIndex * 2] + segmentTree[nodeIndex * 2 + 1];
    }
}  

Frissítés