0

Fenwick 树有一个 update(idx, delta) 函数，可以这样实现：

for ( ; idx < fTree.length; idx += idx & -idx ){
    this._fTree[ idx ] += delta;
}

因此，您正在更新您当前的 idx，然后将您的更改推送到最后。
我想在一个循环中执行几个更新调用，比如

update( 12, 100 );
update( 13, 400 );
update( 17, 200 );

如果我提前知道更新索引的范围（这里是 12 - 17），更新可能会被优化。与其每次都推到最后，我们可以推到某个索引，缓冲剩余的变化，然后在最后一次更新后，将缓冲的变化推到最后。提供图片解释概念：
文本
例如取范围 3 - 7。
更新索引 3 将导致更新以下索引：3 - 4 - 8 - 16。
更新索引 4 将导致：4 - 8 - 16
更新索引 5 将导致：5 - 6 - 8 - 16

最好将所有内容推到 8 点，缓冲休息，然后推到 16 点。

问题

有没有更好的方法来找到这个节点推送到（这里是 8 ），知道范围开始和结束？

非理想解决方案

const getLimitIndex = ( from, to ) => {
    let lim = to;
    for( let tmp = lim & -lim; lim - tmp > from; ){
        lim += tmp;
        tmp = lim & -lim;
    }
    return lim;
}
4

0 回答 0