线段树Lazy propagation在特定条件下无法正确更新问题分析

当使用线段树的Lazy Propagation实现区间加法和区间最小值查询时，存在特定场景下结果不正确的问题：

• 初始数组：[88, 23, 58, 10, 47, 66]
• 对区间[1,4]执行加100的更新操作后，懒标记会被标记在对应线段树节点上
• 此时查询整个区间[0,5]的最小值，结果仍为10（原数组中的最小值），但正确结果应该是88（未被更新的第一个元素）

问题根源：查询操作未触达带有懒标记的节点，导致懒标记未被传递，父节点的最小值未得到正确更新；同时代码中存在多处逻辑错误，比如笔误、懒标记传递逻辑错误、父节点状态未同步更新等。

错误代码示例 #

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){
        // 叶子节点
        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;
        // 逻辑错误：当前节点tree不应累加tag，仅需传递给子节点
        this.tag[left] += this.tag[vertex];
        this.tag[right] += this.tag[vertex];
        this.tree[vertex] += this.tag[vertex];
        this.tag[vertex] = 0;
    }
}

const arr = [88, 23, 58, 10, 47, 66];
const tree = new SegmentTree(arr);
console.log(`更新前最小值：${tree.queryRange(0, 0, arr.length - 1, 0, 5)}`);
tree.updateRange(0, 0, arr.length - 1, 1, 4, 100);
console.log(`更新后最小值：${tree.queryRange(0, 0, arr.length - 1, 0, 5)}`);

修正后的代码及说明 #

关键修正点 #

1. 修复update函数的笔误，确保更新正确的子节点
2. updateRange中添加懒标记传递步骤，处理部分覆盖前先同步子节点状态
3. 更新子节点后重新计算父节点的最小值（结合子节点的tree和tag）
4. 修正push函数逻辑：仅将懒标记传递给子节点，当前节点仅清零tag
5. 优化queryRange的边界判断，确保所有查询路径都能正确触发懒标记传递

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){
        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(rangeEnd < start || rangeStart > end){
            return Infinity;
        }
        // 查询范围完全覆盖当前节点
        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;

        const leftMin = this.queryRange(left, start, mid, rangeStart, rangeEnd);
        const rightMin = this.queryRange(right, mid + 1, end, rangeStart, rangeEnd);

        return Math.min(leftMin, rightMin);
    }

    update(vertex, start, end, pos, value){
        if(start === end){
            this.tree[vertex] = value;
            this.arr[pos] = value;
            return;
        }

        this.push(vertex);
        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(right, mid + 1, end, pos, value);
        }

        this.tree[vertex] = Math.min(
            this.tree[left] + this.tag[left],
            this.tree[right] + this.tag[right]
        );
    }

    updateRange(vertex, start, end, rangeStart, rangeEnd, value){
        if(rangeEnd < start || rangeStart > end){
            return;
        }
        if(rangeStart <= start && rangeEnd >= end){
            this.tag[vertex] += value;
            return;
        }

        this.push(vertex);
        const mid = Math.floor((start + end) / 2);
        const left = 2 * vertex + 1;
        const right = 2 * vertex + 2;

        this.updateRange(left, start, mid, rangeStart, rangeEnd, value);
        this.updateRange(right, mid + 1, end, rangeStart, rangeEnd, value);

        this.tree[vertex] = Math.min(
            this.tree[left] + this.tag[left],
            this.tree[right] + this.tag[right]
        );
    }

    push(vertex){
        const left = 2 * vertex + 1;
        const right = 2 * vertex + 2;
        // 仅当存在子节点时传递标记，避免数组越界
        if(this.tree[left] !== undefined){
            this.tree[left] += this.tag[vertex];
            this.tag[left] += this.tag[vertex];
        }
        if(this.tree[right] !== undefined){
            this.tree[right] += this.tag[vertex];
            this.tag[right] += this.tag[vertex];
        }
        this.tag[vertex] = 0;
    }
}

const arr = [88, 23, 58, 10, 47, 66];
const tree = new SegmentTree(arr);
console.log(`更新前最小值：${tree.queryRange(0, 0, arr.length - 1, 0, 5)}`); // 输出10
tree.updateRange(0, 0, arr.length - 1, 1, 4, 100);
console.log(`更新后最小值：${tree.queryRange(0, 0, arr.length - 1, 0, 5)}`); // 输出88

内容的提问来源于stack exchange，提问作者just_code_dog