一个通用的优化的想法

来源:2-7 封装更加通用的 SQRT 分解数据结构

Wonwayshon

2021-06-04 14:51:49

由于blocks中存储的元素都是整组中每个元素merge出来的属于一个组的特征值,那么我思考如果将这个值与传入的val进行merge如果结果仍然是val那么就可以直接更新?老师看看这个想法正确吗?

新增代码为:

if(merger.merge(blocks[b],val)==val){
            blocks[b]=val;
            return;
        }

update部分代码:

public void update(int index, E val){

        if(index < 0 || index >= N) return;

        int b = index / B;
        data[index] = val;
        
        if(merger.merge(blocks[b],val)==val){
            blocks[b]=val;
            return;
        }

        blocks[b] = data[b * B];
        for(int i = b * B + 1; i < Math.min((b + 1) * B, N); i ++)
            blocks[b] = merger.merge(blocks[b], data[i]);
    }


写回答

1回答

liuyubobobo

2021-06-05

对区间和不成立。


比如 [-1, 1] 的区间和是 0, 现在要把 -1 位置的元素更新为 0,此时满足 -1 + 1 + 0 === 0,但是更新以后,[0, 1] 的和是 1。


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2636 学习 · 1090 问题

查看课程