1310.子数组异或查询

链接：1310.子数组异或查询
难度：Medium
标签：位运算、数组、前缀和
简介：有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]，返回一个包含给定查询 queries 所有结果的数组。

题解 1 - typescript

• 编辑时间：2021-05-12
• 执行用时：1492ms
• 内存消耗：52.9MB
• 编程语言：typescript
• 解法介绍：直接循环异或。

function xorQueries(arr: number[], queries: number[][]): number[] {
  return queries.map(([start, end]) => {
    let ans!: number;
    for (let i = start; i <= end; i++) {
      if (ans) ans ^= arr[i];
      else ans = arr[i];
    }
    return ans;
  });
}

题解 2 - typescript

• 编辑时间：2021-05-12
• 执行用时：132ms
• 内存消耗：53.2MB
• 编程语言：typescript
• 解法介绍：前缀和。

function xorQueries(arr: number[], queries: number[][]): number[] {
  let num = arr[0];
  const prefixSumList: number[] = arr.map((v, i) => (i === 0 ? num : (num ^= v)));
  return queries.map(([start, end]) => prefixSumList[start - 1] ^ prefixSumList[end]);
}

题解 3 - typescript

• 编辑时间：2021-11-14
• 执行用时：124ms
• 内存消耗：52.7MB
• 编程语言：typescript
• 解法介绍：树状数组。

class FenwickTree {
  private arr: number[];
  constructor(private n: number) {
    this.arr = new Array(n + 1).fill(0);
  }
  add(idx: number, num: number): void {
    while (idx <= this.n) {
      this.arr[idx] += num;
      idx += this.lowbit(idx);
    }
  }
  at(idx: number): number {
    return this.query(idx) - this.query(idx - 1);
  }
  query(idx: number): number {
    let sum = 0;
    while (idx) {
      sum += this.arr[idx];
      idx -= this.lowbit(idx);
    }
    return sum;
  }
  private lowbit(num: number) {
    return num & -num;
  }
}
class StreamRank {
  tree = new FenwickTree(50001);
  track(x: number): void {
    this.tree.add(x + 1, 1);
  }
  getRankOfNumber(x: number): number {
    return this.tree.query(x + 1);
  }
}