js 这个for循环嵌套for循环有什么可以优化的地方吗

Question

数组格式如下

const arr1 = [
  ...
  [1000, 7000], // arr2需要如果满足下标便加1 [开始下标, 结束下标]
  [2000, 5000],
  [4000, 9000],
  [3000, 6700],
  ...
]
const arr2 = [
  ...
  {
    value: 0
  },
  {
    value: 0
  }
  ...
]

arr1 与 arr2 的length都很长，几千左右

for (const item of arr1) {

  for (const i = 0; i < arr2.length; i++) {
  
    if (i > item[0] && i < item[1]) {
    
      arr2[i].value = arr2[i].value + 1
      
    }
    
  }
  
}

我现在用for实现，但我觉得循环量太大，请问有没有什么可以优化的地方呢

Answer 1

方法一(推荐): 差分数组求前缀和 时间复杂度O(N)其中N为区间的最大下标值

const acc = (a, n) => {
  const delta = Array.from({ length: n + 2 }).fill(0);

  for (const [s, e] of a) {
    delta[s] += 1;
    delta[e + 1] -= 1;
  }

  const ans = Array.from({ length: n + 1 }).fill(0);

  ans[0] = delta[0];
  for (let i = 1; i <= n; ++i) {
    ans[i] += delta[i] + ans[i - 1];
  }

  return ans;
};

console.log(
  acc(
    [
      [0, 10],
      [9, 10],
      [8, 15],
      [20, 30]
    ],
    30
  )
);

方法二: 线段树时间复杂度O(N*logN),其中N为所有区间中最大的下标值,时间复杂度变高了但是支持动态的更新和删除区间

class SegmentTree {
  private cur = 0;
  private add: number[];
  private sum: number[];

  constructor(data: number[]) {
    this.add = Array.from<number>({ length: data.length << 2 }).fill(0);
    this.sum = Array.from<number>({ length: data.length << 2 }).fill(0);
    this.build(1, data.length, 1, data);
  }

  push_up(rt: number): void {
    const { sum } = this;
    sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1];
  }

  push_down(rt: number, m: number): void {
    const { add, sum } = this;
    if (add[rt]) {
      add[rt << 1] += add[rt];
      add[(rt << 1) | 1] += add[rt];
      sum[rt << 1] += add[rt] * (m - (m >> 1));
      sum[(rt << 1) | 1] += add[rt] * (m >> 1);
      add[rt] = 0;
    }
  }

  build(l: number, r: number, rt: number, desc: number[]): void {
    const { add, sum } = this;
    add[rt] = 0;
    if (l === r) {
      sum[rt] = desc[this.cur++];
      return;
    }
    const m = (l + r) >> 1;
    this.build(l, m, rt * 2, desc);
    this.build(m + 1, r, rt * 2 + 1, desc);
    this.push_up(rt);
  }

  update(
    L: number,
    R: number,
    c: number,
    l: number,
    r: number,
    rt: number
  ): void {
    const { add, sum } = this;
    if (L <= l && r <= R) {
      add[rt] += c;
      sum[rt] += c * (r - l + 1);
      return;
    }
    this.push_down(rt, r - l + 1);
    const m = (l + r) >> 1;
    if (L <= m) {
      this.update(L, R, c, l, m, rt << 1);
    }
    if (m < R) {
      this.update(L, R, c, m + 1, r, (rt << 1) | 1);
    }
    this.push_up(rt);
  }

  query(L: number, R: number, l: number, r: number, rt: number): number {
    const { sum } = this;
    if (L <= l && r <= R) {
      return sum[rt];
    }
    this.push_down(rt, r - l + 1);
    const m = (l + r) >> 1;
    let ret = 0;
    if (L <= m) ret += this.query(L, R, l, m, rt * 2);
    if (m < R) ret += this.query(L, R, m + 1, r, rt * 2 + 1);
    return ret;
  }
}

const acc = (a: number[][], n: number) => {
  const st = new SegmentTree(
    Array.from<number>({ length: n + 1 }).fill(0)
  );

  for (const [s, e] of a) {
    st.update(s + 1, e + 1, 1, 1, n + 1, 1);
  }

  const ans = [];

  for (let i = 1; i <= n + 1; ++i) {
    ans[i - 1] = st.query(i, i, 1, n + 1, 1);
  }

  return ans;
};

console.log(
  acc(
    [
      [0, 10],
      [9, 10],
      [8, 15],
      [20, 30]
    ],
    30
  )
);

Answer 2

arr 1 构建树（要想想怎么构建）

遍历 arr2 判断是否找到节点。

Answer 3

看了一眼，是区间操作，可以上线段树

参考 OI-wiki