[关闭]
@Yano 2016-03-22T03:54:33.000000Z 字数 1340 阅读 3538

LeetCode 307 Range Sum Query - Mutable

LeetCode


题目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

分析

LeetCode 303 的数组是不可变的,本题的数组是可变的。可以使用树状数组维基百科链接,不再具体介绍(不重复造轮子)。

树状数组(Fenwick_tree),最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables1为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和。它可以以O(\log n)的时间得到\sum_{i=1}^N a[i],并同样以O(\log n)对某项加一个常数。

初始化复杂度最优为O(N\log N)
单次询问复杂度O(\log N),其中N为数组大小
单次修改复杂度O(\log N),其中N为数组大小
空间复杂度O(N)

1.png-25.1kB

代码

  1. public class NumArray {
  2. // array存储 nums数组,helper用来维护array的前缀和
  3. int[] array, helper;
  4. public NumArray(int[] nums) {
  5. array = new int[nums.length];
  6. helper = new int[nums.length + 1];
  7. for (int i = 0; i < nums.length; i++) {
  8. array[i] = nums[i];
  9. }
  10. for (int i = 0; i < nums.length; i++) {
  11. add(i + 1, nums[i]);
  12. }
  13. }
  14. private void add(int pos, int value) {
  15. while (pos < helper.length) {
  16. helper[pos] += value;
  17. pos += lowBit(pos);
  18. }
  19. }
  20. // 预备函数,返回参数转为二进制后,最后一个1的位置所代表的数值
  21. private int lowBit(int pos) {
  22. return pos & (-pos);
  23. }
  24. private int sum(int pos) {
  25. int rt = 0;
  26. while (pos > 0) {
  27. rt += helper[pos];
  28. pos -= lowBit(pos);
  29. }
  30. return rt;
  31. }
  32. void update(int i, int val) {
  33. int delta = val - array[i];
  34. array[i] = val;
  35. add(i + 1, delta);
  36. }
  37. public int sumRange(int i, int j) {
  38. return sum(j + 1) - sum(i);
  39. }
  40. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注