方法一:树状数组
class NumArray { int[] nums; int[] bitArr; int n; public NumArray(int[] nums) { n = nums.length; this.nums = nums; bitArr = new int[n+1]; for(int i = 1; i <= n; i++) bitArr[i] = nums[i-1]; for(int i = 1; i <= n; i++) { int j = i + lowbit(i); if(j <= n) bitArr[j] += bitArr[i]; } } public int lowbit(int x) {return x&(-x);} public void update(int i, int val) { int diff = val - nums[i]; nums[i] = val; i++; for(int j = i; j <= n; j += lowbit(j)) { bitArr[j] += diff; } } public int prefixSum(int x) { int res = 0; x++; for(int i = x; i > 0; i -= lowbit(i)) { res += bitArr[i]; } return res; } public int sumRange(int i, int j) { return prefixSum(j) - prefixSum(i-1); } }
方法二:线段树
class NumArray { private Node root; int[] nums; public NumArray(int[] nums) { if(nums != null && nums.length > 0) { this.nums = nums; root = new Node(0,nums.length-1); // 根节点包含全部区间 buildTree(root); // 建树 } } public int buildTree(Node root) { int l = root.l, r = root.r; if(l == r) { // 递归终止条件为到达叶节点 root.sum = nums[l]; return root.sum; } int mid = (l + r) / 2; root.left = new Node(l,mid); root.right = new Node(mid+1,r); int lval = buildTree(root.left); int rval = buildTree(root.right); // 左右递归建树, 返回值为区间和 root.sum = lval + rval; return root.sum; } public void update(int i, int val) { set(root,i,val); } public void set(Node root, int i, int val) { //递归更新单值 if(root.l == root.r && root.l == i) { root.sum = val; // 终止条件为找到单值 return; } int l = root.l, r = root.r; int mid = (l + r) / 2; if(i <= mid) { set(root.left,i,val); } else { set(root.right,i,val); } // 每次递归结束回到上一个递归栈都要同时跟新父节点的区间和 root.sum = root.left.sum + root.right.sum; return; } public int sumRange(int i, int j) { return query(i,j,root); } public int query(int i, int j, Node root) { // 递归查询某一段区间和 if(root.l == i && root.r == j) { return root.sum;// 递归终止条件为找到这一段区间,返回区间和 } int mid = (root.l + root.r) / 2; if(i > mid) { // [l,mid]为左子树 i > mid 向右子树递归 return query(i,j,root.right); } if(j < mid + 1) { // [mid+1,r]为右子树 j < mid+1 向左子树递归 return query(i,j,root.left); } //这种情况为i与j在mid两端所以要取[i,mid]和[mid+1,j]的和 return query(i,mid,root.left) + query(mid+1,j,root.right); } } class Node { //定义区间树的节点 int l, r; // 区间的左值和右值 int sum; // 区间总和 Node left,right; // 左右节点 public Node(int l, int r) { this.l = l; this.r = r; } }