如何降低这个问题的时间复杂度呢？

Question

在经历了长期困难的编码挑战之后，有一个问题困扰着我。我思考了足够的时间，但找不到解决的方法。在这里，我在下面提供一个问题和示例。

输入

• v ：数字数组。
• q ：二维数组，嵌套数组中有 3 个元素。

描述

v是一个数组，q是一个根据其嵌套元素执行不同操作的命令。

如果嵌套数组的第一个元素1=> 嵌套数组的第二个和第三个元素成为索引并返回sum[second:third+1]（如您所见，它是包含的）

如果嵌套数组的第一个元素是2=>第二个索引的元素成为第三个。与...一样v[second] = third

输入示例

• v：[1,2,3,4,5]
• q : [[1,2,4], [2,3,8], [1,2,4]]

例子

通过提供的示例，它就像

1. 命令是[1,2,4]=> 第一个元素是1。v[2]它应该返回从到（含）=> 12的总和v[4]。
2. 命令是[2,3,8]=> 第一个元素是2。它切换v[3]到8。（现在 v 是[1,2,3,8,5]）
3. 命令是[1,2,4]=> 第一个元素是1。它应该返回总和从v[2]to v[4]（含）=> 16，因为第三个索引已从上一个命令更改。

所以最终答案是[12, 16]

问题。

下面的代码是我解决的方法，但是，这是 O(n**2) 复杂度。我想知道在这种情况下如何降低时间复杂度。

我尝试创建一个哈希对象，但没有成功。在这种情况下我想不出一个好的方法来制作缓存。

function solution(v, q) {
  let answer = [];
  for (let i = 0; i < q.length; i++) {
    let [a, b, c] = q[i];
    if (a === 1) {
      let sum = 0;
      for (let i = b; i <= c; i++) {
        sum += v[i];
      }
      answer.push(sum);
    } else if (a === 2) {
      v[b] = c;
    }
  }
  return answer;
}

Answer 1

此类问题通常可以使用芬威克树更有效地解决

这是一个实现：

class BinaryIndexedTree extends Array {
    constructor(length) {
        super(length + 1);
        this.fill(0);
    }
    add(i, delta) {
        i++; // make index 1-based
        while (i < this.length) {
            this[i] += delta;
            i += i & -i; // add least significant bit
        }
    }
    sumUntil(i) {
        i++; // make index 1-based
        let sum = 0;
        while (i) {
            sum += this[i];
            i -= i & -i;
        }
        return sum;
    }
}

function solution(values, queries) {
    const tree = new BinaryIndexedTree(values.length);
    values.forEach((value, i) => tree.add(i, value));
    
    const answer = [];
    for (const [a, b, c] of queries) {
        if (a === 1) {
            answer.push(tree.sumUntil(c) - tree.sumUntil(b - 1));
        } else {
            tree.add(b, c - values[b]);
            values[b] = c;
        }
    }
    
    return answer;
}

let answer = solution([1,2,3,4,5], [[1,2,4], [2,3,8], [1,2,4]]);
console.log(answer);

时间复杂度

tree.add运行或一次的时间复杂度tree.sumUntil为 O(log)，其中 是输入值的大小 ( values.length)。所以这也是运行一个查询的时间复杂度。

• 树的创建成本为 O()，因为这是树的大小
• 树的初始化values成本为 O(log)，因为实际上输入中的每个值都充当将值从 0 更新为实际值的查询。
• 执行查询的成本为 O(log)，其中 是查询数量 ( queries.length)

所以总的来说，我们的时间复杂度为 O( + log + log) = O((+)log)

进一步阅读

有关 Fenwick 树的更多信息，请参阅BIT：二叉索引树背后的直觉是什么以及它是如何被考虑的？