For example, here is a array [88, 23, 58, 10, 47, 66] and I want to query the min value in a range.
If I add 100 to the range [1,4] with lazy propagation, the lazy tag will be tagged to the segment of range [1,4].
However, if I query the range [0,5], the result will be still 10 because it doesn't reach the segment [1,4].
the code example in Javascript:
class SegmentTree {
constructor(arr){
this.arr = arr;
this.tree = new Array(4 * arr.length);
this.tag = new Array(4 * arr.length).fill(0);
this.buildTree(0, 0, arr.length - 1);
}
buildTree(vertex, start, end){
// the end node
if(start === end){
this.tree[vertex] = this.arr[start];
return;
}
const mid = Math.floor((start + end) / 2);
const left = 2 * vertex + 1;
const right = 2 * vertex + 2;
this.buildTree(left, start, mid);
this.buildTree(right, mid + 1, end);
this.tree[vertex] = Math.min(this.tree[left], this.tree[right]);
}
queryRange(vertex, start, end, rangeStart, rangeEnd){
if(rangeStart === start && rangeEnd === end){
return this.tree[vertex] + this.tag[vertex];
}
this.push(vertex);
const mid = Math.floor((start + end) / 2);
const left = 2 * vertex + 1;
const right = 2 * vertex + 2;
if(rangeStart > mid){
return this.queryRange(right, mid + 1, end, rangeStart, rangeEnd);
} else if(rangeEnd <= mid){
return this.queryRange(left, start, mid , rangeStart, rangeEnd);
} else {
return Math.min(this.queryRange(left, start, mid, rangeStart, mid), this.queryRange(right, mid + 1, end, mid + 1, rangeEnd));
}
}
update(vertex, start, end, pos, value){
if(start === end){
this.tree[vertex] = value;
this.arr[pos] = value;
return;
}
const mid = Math.floor((start + end) / 2);
const left = 2 * vertex + 1;
const right = 2 * vertex + 2;
if(pos >= start && pos <= mid){
this.update(left, start, mid, pos, value);
} else {
this.update(left, mid + 1, end, pos, value);
}
this.tree[vertex] = Math.min(this.tree[left], this.tree[right]);
}
updateRange(vertex, start, end, rangeStart, rangeEnd, value){
if(rangeStart <= start && rangeEnd >= end){
this.tag[vertex] += value;
return;
}
const mid = Math.floor((start + end) / 2);
const left = 2 * vertex + 1;
const right = 2 * vertex + 2;
if(rangeStart > mid){
this.updateRange(right, mid + 1, end, rangeStart, rangeEnd, value);
} else if(rangeEnd <= mid){
this.updateRange(left, start, mid , rangeStart, rangeEnd, value);
} else {
this.updateRange(right, mid + 1, end, rangeStart, rangeEnd, value);
this.updateRange(left, start, mid , rangeStart, rangeEnd, value);
}
}
push(vertex){
const left = 2 * vertex + 1;
const right = 2 * vertex + 2;
this.tag[left] += this.tag[vertex];
this.tag[right] += this.tag[vertex];
this.tree[vertex] += this.tag[vertex];
this.tag[vertex] = 0;
}
}
const sum = [88, 23, 58, 10, 47, 66];
const tree = new SegmentTree(sum);
console.log(`before update: ${tree.queryRange(0, 0, sum.length - 1, 0, 5)}`);
tree.updateRange(0, 0, sum.length - 1, 1, 4, 100);
console.log(`after update: ${tree.queryRange(0, 0, sum.length - 1, 0, 5)}`);
Finally, I solved the problem. It is because I hasn't merged up the two child nodes after updated range.
The updated code: