真是醉了，每次写线段树都会出现各种边界问题，这次也是，看了半天也没有看出来，到底哪里有问题？
用二叉树实现的线段树
测试用例总是出错，而且还是其中一个book出错。
更奇怪的是，修改线段树的初始化上限，1e9改成 100 1000 10000，出错的测试用例就可以通过了。
哪位大佬上眼，帮忙看下哪里有bug呢？
731.My Calendar II
代码如下：
class MyCalendarTwo {
Node root;
public MyCalendarTwo() {
root = new Node(0, (int)1e9);
}
public boolean book(int start, int end) {
int cur = query(root, start, end - 1);
if (cur > 1) {
return false;
}
update(root, start, end - 1, 1);
return true;
}
class Node {
int left;
int right;
int mark;
int val;
Node leftNode;
Node rightNode;
public Node(int left, int right) {
this.left = left;
this.right = right;
}
public Node getLeft() {
if (leftNode == null) {
leftNode = new Node(left, left + (right - left) / 2);
}
return leftNode;
}
public Node getRight() {
if (rightNode == null) {
rightNode = new Node(left + (right - left) / 2 + 1, right);
}
return rightNode;
}
}
private void pushDown(Node node) {
if (node.mark > 0) {
node.getLeft().val += node.mark;
node.getRight().val += node.mark;
node.leftNode.mark += node.mark;
node.rightNode.mark += node.mark;
node.mark = 0;
}
}
public void update(Node node, int lo, int hi, int val) {
if (node.left > hi || node.right < lo) {
return;
}
if (node.left >= lo && node.right <= hi) {
node.val += val;
node.mark += val;
} else {
pushDown(node);
update(node.getLeft(), lo, hi, val);
update(node.getRight(), lo, hi, val);
node.val = Math.max(node.leftNode.val, node.rightNode.val);
}
}
public int query(Node node, int lo, int hi) {
if (node == null || node.left > hi || node.right < lo) {
return 0;
}
if (node.left >= lo && node.right <= hi) {
return node.val;
}
pushDown(node);
//问题出在这里，query的时候不需要向上更新，因为update的时候已经向上更新过了。query是查询符合要求区间的结果，这种return 0的写法会忽略有值但不符合区间要求的节点，导致错误地更新了父节点。
//node.val = Math.max(query(node.leftNode, lo, hi), query(node.rightNode, lo, hi));
//return node.val;
return Math.max(query(node.leftNode, lo, hi), query(node.rightNode, lo, hi));
}
}出错的测试用例如下：
最后一次错了
输入
["MyCalendarTwo","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book"]
[[],[22,29],[12,17],[20,27],[27,36],[24,31],[23,28],[47,50],[23,30],[24,29],[19,25],[19,27],[3,9],[34,41],[22,27],[3,9],[29,38],[34,40],[49,50],[42,48],[43,50],[39,44],[30,38],[42,50],[31,39],[9,16],[10,18],[31,39],[30,39],[48,50],[36,42]]输出
[null,true,true,true,true,false,false,true,false,false,false,false,true,true,false,true,false,false,true,true,false,true,false,false,false,true,false,false,false,false,true]预期结果
[null,true,true,true,true,false,false,true,false,false,false,false,true,true,false,true,false,false,true,true,false,true,false,false,false,true,false,false,false,false,false]评论 (2)
