Range Sum Query"/>
307. Range Sum Query
题目:
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:
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
链接: /
题解:
这应该算是Range Query的经典题目之一了。也是通过这道题我第一次接触到了Segment Tree,也对Fenwick Tree有了一点了解。下面是用Segment Tree来做的。 Segment Tree线段树每一个节点都是一段线段,有start和end,然后还可以有其他的值,比如区间和sum,区间最大值max,区间最小值min。我们可以用自底向上构建二叉树的方式构建Segment Tree,这个过程也有点类似于Bottom-up的merge sort,思想也是Divide and Conquer。完毕之后就可以在O(logn)的时间update,或者得到range Sum。其实更好的方法是使用Fenwick Tree, Fenwick Tree(Binary Indexed Tree)在处理Range Query真的是一绝,构造简练,原理也精妙,还可以扩展到多维,一定要好好学一学。
Time Complexity - O(n) build, O(logn) update, O(logn) rangeSum, Space Complexity - O(n)
public class NumArray {private class SegmentTreeNode {public int start;public int end;public int sum;public SegmentTreeNode left, right;public SegmentTreeNode(int start, int end) {this.start = start;this.end = end;this.sum = 0;}}private SegmentTreeNode root;public NumArray(int[] nums) {this.root = buildTree(nums, 0, nums.length - 1); }public void update(int i, int val) {update(root, i, val);}private void update(SegmentTreeNode node, int position, int val) {if(node.start == position && node.end == position) {node.sum = val;return;}int mid = node.start + (node.end - node.start) / 2;if(position <= mid) {update(node.left, position, val);} else {update(node.right, position, val);}node.sum = node.left.sum + node.right.sum;}public int sumRange(int i, int j) {return sumRange(root, i, j);}private int sumRange(SegmentTreeNode node, int lo, int hi) {if(node.start == lo && node.end == hi) {return node.sum;}int mid = node.start + (node.end - node.start) / 2;if(hi <= mid) {return sumRange(node.left, lo, hi);} else if (lo > mid) {return sumRange(node.right, lo, hi);} else {return sumRange(node.left, lo, mid) + sumRange(node.right, mid + 1, hi);}}private SegmentTreeNode buildTree(int[] nums, int lo, int hi) {if(lo > hi) {return null;} else {SegmentTreeNode node = new SegmentTreeNode(lo, hi);if(lo == hi) {node.sum = nums[lo];} else {int mid = lo + (hi - lo) / 2;node.left = buildTree(nums, lo, mid);node.right = buildTree(nums, mid + 1, hi);node.sum = node.left.sum + node.right.sum;}return node;}} }// Your NumArray object will be instantiated and called as such: // NumArray numArray = new NumArray(nums); // numArray.sumRange(0, 1); // numArray.update(1, 10); // numArray.sumRange(1, 2);
Fenwick Tree: (Binary Indexed Tree) (树状数组)
很有意思的构建,以数组nums = {1, 2, 3, 4, 5, 6, 7, 8}为例,这个数组长度为8。 跟dynamic programming的预处理很像,我们先建立一个长度为nums.length + 1 = 9的数组BIT。接下来遍历数组nums,对BIT数组进行update(i + 1, nums[i])。这里BIT数组每个值BIT[i]代表nums数组里在i之前的部分元素和。原理是像自然数可以被表示为2n的和一样,把nums数组里到0到i的sum表示成2n的和,从而导致update和rangeSum都可以用O(logn)的时间求出来。这里构建的时候可以有几种写法,主要就是利用当前i的least significante 1来确定到底BIT[i]要保存多少原数组的值。这里借用algorithmist的原话"Every index in the cumulative sum array, say i, is responsible for the cumulative sum from the index i to (i - (1<<r) + 1)。" 构建过程中可以用 (i & -i)来找到least significate 1,之后来进行i = i + (i & -i)来尝试从小到大计算下一个BIT数组中被影响的元素。 而rangeSum的时候则使用i = i - (i & -i)来从大到小查找从0到i - 1的sum。
构建过程 - update, 给定数组nums = {1,2, 3, 4, 5, 6, 7, 8}
BIT[0] = 0
BIT[1] = nums[0] = 1 = 1
BIT[2] = nums[0] + nums[1] = 1 + 2 = 3
BIT[3] = nums[2] = 3 = 3
BIT[4] = nums[0] + nums[1] + nums[2] + nums[3] = 1+ 2 + 3 + 4 = 10
BIT[5] = nums[4] = 5 = 5
BIT[6] = nums[4] + nums[5] = 5 + 6 = 11
BIT[7] = nums[6] = 7 = 7
BIT[8] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5] + nums[6] + nums[7] = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
求Sum过程, 通过 sum = BIT[i + 1]; i = i - (i & -i); 从大到小迭代来计算。
sum(0) = BIT[1]
sum(1) = BIT[2]
sum(2) = BIT[3] + BIT[2]
sum(3) = BIT[4]
sum(4) = BIT[5] + BIT[4]
sum(5) = BIT[6] + BIT[4]
sum(6) = BIT[7] + BIT[6] + BIT[4]
sum(7) = BIT[8]
得到sum(i)以后就可以相减来计算range sum了。
Time Complexity - O(nlogn) build, O(logn) update, O(logn) rangeSum, Space Complexity - O(n)
public class NumArray {private int BIT[]; // Binary Indexed Tree = Fenwick Treeprivate int[] nums;public NumArray(int[] nums) {BIT = new int[nums.length + 1];for(int i = 0; i < nums.length; i++) {init(i + 1, nums[i]);}this.nums = nums;}private void init(int i, int val) {while(i < BIT.length) {BIT[i] += val;i = i + (i & -i);}}public void update(int i, int val) {int delta = val - nums[i];nums[i] = val;init(i + 1, delta);}public int sumRange(int i, int j) {return getSum(j + 1) - getSum(i);}private int getSum(int i) {int sum = 0;while(i > 0) {sum += BIT[i];i = i - (i & -i);}return sum;} }
题外话: 今天去NYU图书馆自习,正值考期,人山人海的。我带了电脑却忘记带插座,无奈只能用Java 在线的编译器/, 不过这个真的还挺好用,除了不能debug,其他都可以,nice。晚上吃了Hakata Tonton,4个人大概人均$50+,并没有想象的那么好吃,以后还是要攒机会去日本玩。 刷题群里大家对Heapify有了热烈的讨论,我自己认为Heapify主要有两种,Bottom-up (swim)和Top-down(sink)。也要复习一下Priority Queue的implementation。要多看Sedgewick的课件和sample code才行。 在GitHub发现有个人叫indy256,实现了好多好多高级数据结构,有2d-fenwick tree,以及O(n)的Suffix Tree。大牛和普通人的距离真的好遥远,我还是继续努力。
二刷:
暂时只用了segment tree。 Fenwick Tree以后再理解。
Java:
Segment Tree:
public class NumArray {private SegmentTreeNode root;private int[] nums;public NumArray(int[] nums) {this.nums = nums;this.root = buildTree(0, nums.length - 1);}void update(int i, int val) {update(root, i, val);}private void update(SegmentTreeNode node, int pos, int val) {if (node == null) return;if (node.start == pos && node.end == pos) {node.val = val;nums[pos] = val;return;}int mid = node.start + (node.end - node.start) / 2;if (pos <= mid) {update(node.left, pos, val);} else {update(node.right, pos, val);}node.val = node.left.val + node.right.val;}public int sumRange(int i, int j) {return sumRange(root, i, j);}private int sumRange(SegmentTreeNode node, int lo, int hi) {if (lo > hi) return 0;if (node.start == lo && node.end == hi) return node.val;int mid = node.start + (node.end - node.start) / 2;if (hi <= mid) {return sumRange(node.left, lo, hi);} else if (lo > mid) {return sumRange(node.right, lo, hi);} else {return sumRange(node.left, lo, mid) + sumRange(node.right, mid + 1, hi);}}private SegmentTreeNode buildTree(int lo, int hi) {if (lo > hi) return null;SegmentTreeNode node = new SegmentTreeNode(lo, hi);if (lo == hi) {node.val = nums[lo];} else {int mid = lo + (hi - lo) / 2;node.left = buildTree(lo, mid);node.right = buildTree(mid + 1, hi);node.val = node.left.val + node.right.val;}return node;}private class SegmentTreeNode {int start;int end;int val;SegmentTreeNode left, right;public SegmentTreeNode(int start, int end) {this.start = start;this.end = end;this.val = 0;}} }// Your NumArray object will be instantiated and called as such: // NumArray numArray = new NumArray(nums); // numArray.sumRange(0, 1); // numArray.update(1, 10); // numArray.sumRange(1, 2);
Reference:
/
.java.html
/
.java.html/
.java.html
.pdf
.java.html
.0480-004/Lecture4.pdf
/
.php/Fenwick_tree
.html
;jsessionid=A4ADC19B8D7E3A202944A808F5840D21?doi=10.1.1.14.8917&rep=rep1&type=pdf
.6093v5.pdf
更多推荐
307. Range Sum Query
发布评论