在类的构造函数中给一个整数数组, 实现两个方法
query(start, end)和modify(index, value):
- 对于 query(start, end), 返回数组中下标 start 到 end 的 和。
- 对于 modify(index, value), 修改数组中下标为 index 上的数为 value.
注意事项
在做此题前，建议先完成以下三题：
代码
- 写法1
public class Solution {
/* you may need to use some attributes here */
/*
* @param A: An integer array
*/
public class SegmentTreeNode {
public int start;
public int end;
public int sum;
public SegmentTreeNode left;
public SegmentTreeNode right;
public SegmentTreeNode(int start,
int end,
int sum) {
this.start = start;
this.end = end;
this.sum = sum;
this.left = null;
this.right = null;
}
}
public SegmentTreeNode buildHelper(int start, int end, int[] A) {
if (start > end) {
return null;
}
if (start == end) {
return new SegmentTreeNode(start, end, A[start]);
}
int mid = start + (end - start) / 2;
// root.sum 的初值应该是 0，不能写 A[0]
SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
root.left = buildHelper(start, mid, A);
root.right = buildHelper(mid + 1, end, A);
if (root.left != null) {
root.sum += root.left.sum;
}
if (root.right != null) {
root.sum += root.right.sum;
}
return root;
}
public long querySegmentTreeNode(SegmentTreeNode root, int start, int end) {
if (start <= root.start && root.end <= end) {
return root.sum;
}
int mid = root.start + (root.end - root.start) / 2;
long ans = 0;
if (start <= mid) {
ans += querySegmentTreeNode(root.left, start, end);
}
if (end > mid) {
ans += querySegmentTreeNode(root.right, start, end);
}
return ans;
}
public void modifySegmentTreeNode(SegmentTreeNode root, int index, int value) {
if (root.start == root.end && root.start == index) {
root.sum = value;
return;
}
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modifySegmentTreeNode(root.left, index, value);
} else {
modifySegmentTreeNode(root.right, index, value);
}
root.sum = root.left.sum + root.right.sum;
}
SegmentTreeNode root;
public Solution(int[] A) {
// do intialization if necessary
root = buildHelper(0, A.length - 1, A);
}
/*
* @param start: An integer
* @param end: An integer
* @return: The sum from start to end
*/
public long query(int start, int end) {
return querySegmentTreeNode(root, start, end);
}
/*
* @param index: An integer
* @param value: An integer
* @return: nothing
*/
public void modify(int index, int value) {
modifySegmentTreeNode(root, index, value);
}
}
- 另一种写法
public class Solution {
/* you may need to use some attributes here */
class SegmentTreeNode {
public int start, end;
public int sum;
public SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
this.left = this.right = null;
}
}
SegmentTreeNode root;
public SegmentTreeNode build(int start, int end, int[] A) {
// write your code here
if(start > end) { // check core case
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
if(start != end) {
int mid = (start + end) / 2;
root.left = build(start, mid, A);
root.right = build(mid+1, end, A);
root.sum = root.left.sum + root.right.sum;
} else {
root.sum = A[start];
}
return root;
}
public int querySegmentTree(SegmentTreeNode root, int start, int end) {
// write your code here
if(start == root.start && root.end == end) { // 相等
return root.sum;
}
int mid = (root.start + root.end)/2;
int leftsum = 0, rightsum = 0;
// 左子区
if(start <= mid) {
if( mid < end) { // 分裂
leftsum = querySegmentTree(root.left, start, mid);
} else { // 包含
leftsum = querySegmentTree(root.left, start, end);
}
}
// 右子区
if(mid < end) { // 分裂 3
if(start <= mid) {
rightsum = querySegmentTree(root.right, mid+1, end);
} else { // 包含
rightsum = querySegmentTree(root.right, start, end);
}
}
// else 就是不相交
return leftsum + rightsum;
}
public void modifySegmentTree(SegmentTreeNode root, int index, int value) {
// write your code here
if(root.start == index && root.end == index) { // 查找到
root.sum = value;
return;
}
// 查询
int mid = (root.start + root.end) / 2;
if(root.start <= index && index <=mid) {
modifySegmentTree(root.left, index, value);
}
if(mid < index && index <= root.end) {
modifySegmentTree(root.right, index, value);
}
//更新
root.sum = root.left.sum + root.right.sum;
}
/**
* @param A: An integer array
*/
public Solution(int[] A) {
// write your code here
root = build(0, A.length-1, A);
}
/**
* @param start, end: Indices
* @return: The sum from start to end
*/
public long query(int start, int end) {
// write your code here
return querySegmentTree(root, start ,end);
}
/**
* @param index, value: modify A[index] to value.
*/
public void modify(int index, int value) {
// write your code here
modifySegmentTree(root, index, value);
}
}
网友评论