307.区域和检索-数组可修改

链接：307.区域和检索-数组可修改
难度：Medium
标签：设计、树状数组、线段树、数组
简介：给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

题解 1 - typescript

• 编辑时间：2021-11-14
• 执行用时：532ms
• 内存消耗：70.5MB
• 编程语言：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 NumArray {
  private tree: FenwickTree;
  constructor(nums: number[]) {
    this.tree = new FenwickTree(nums.length);
    for (let i = 0; i < nums.length; i++) {
      this.tree.add(i + 1, nums[i]);
    }
  }
  update(index: number, val: number): void {
    this.tree.add(index + 1, val - this.tree.at(index + 1));
  }
  sumRange(left: number, right: number): number {
    return this.tree.query(right + 1) - this.tree.query(left);
  }
}

题解 2 - cpp

• 编辑时间：2022-04-04
• 执行用时：372ms
• 内存消耗：146.4MB
• 编程语言：cpp
• 解法介绍：树状数组。

class FenwickTree {
   public:
    int n;
    vector<int> arr;
    FenwickTree(int n) : n(n + 1), arr(vector<int>(n + 1, 0)) {}
    int lowbit(int num) { return num & -num; }
    void add(int idx, int num) {
        idx += 1;
        while (idx < n) {
            arr[idx] += num;
            idx += lowbit(idx);
        }
    }
    int at(int idx) { return query(idx) - query(idx - 1); }
    int query(int idx) {
        idx += 1;
        int num = 0;
        while (idx) {
            num += arr[idx];
            idx -= lowbit(idx);
        }
        return num;
    }
};
class NumArray {
   public:
    FenwickTree tree;
    NumArray(vector<int>& nums) : tree(nums.size()) {
        for (int i = 0; i < nums.size(); i++) {
            tree.add(i, nums[i]);
        }
    }
    void update(int index, int val) { tree.add(index, val - tree.at(index)); }
    int sumRange(int left, int right) {
        return tree.query(right) - tree.query(left - 1);
    }
};

题解 3 - python

• 编辑时间：2023-11-13
• 执行用时：1216ms
• 内存消耗：33.27MB
• 编程语言：python
• 解法介绍：树状数组。

class FenwickTree:
    def __init__(self, n: int):
        self.n = n
        self.arr = [0] * (n + 1)
    def add(self, idx: int, num: int):
        while idx <= self.n:
            self.arr[idx] += num
            idx += self.lowbit(idx)
    
    def query(self, idx: int) -> int:
        sum = 0
        while idx > 0:
            sum += self.arr[idx]
            idx -= self.lowbit(idx)
        return sum
    
    def at(self, idx: int) -> int:
        return self.query(idx) - self.query(idx - 1)
    def range(self, left: int, right: int) -> int:
        return self.query(right) - self.query(left - 1)
    def lowbit(self, num: int) -> int:
        return num & -num
class NumArray:
    def __init__(self, nums: List[int]):
        self.tree = FenwickTree(len(nums))
        self.nums = nums
        for i, num in enumerate(nums): self.tree.add(i + 1, num)
    def update(self, index: int, val: int) -> None:
        self.tree.add(index + 1, val - self.nums[index])
        self.nums[index] = val
    def sumRange(self, left: int, right: int) -> int:
        return self.tree.range(left + 1, right + 1)