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

Question

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

输入

• v : 数字数组。
• q : 嵌套数组中包含 3 个元素的二维数组。

描述

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

如果嵌套数组的第一个元素是 1 => 嵌套数组的第二个和第三个元素成为 index 并且 returns 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。它应该 return 从 v[2] 到 v[4] （含）=> 12.
2. 命令是 [2,3,8] => 第一个元素是 2。它将 v[3] 切换为 8。 （现在 v 是 [1,2,3,8,5]）
3. 命令是 [1,2,4] => 第一个元素是 1。它应该 return 从 v[2] 到 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

此类问题通常可以通过 Fenwick tree

更有效地解决

这是一个实现：

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: What is the intuition behind a binary indexed tree and how was it thought about?