线段树区间查询传参的疑问

Question

如上图所示，// 在以treeIndex为根的线段树中[l…r]的范围里，搜索区间[queryL…queryR]的值, 既然是这样，当 queryL >=mid+1时，原文中的
query(rightTreeIndex, mid + 1, r, queryL, queryR), 第2个参数mid+1我认为可以直接换成 queryL, 毕竟 [queryL, queryR]也是在 [queryL, r]这个区内的，老师就是这里我表示不解，因为我自己试了，换成我图中的传参方式，计算结果就错了，不知道怎么回事:)

Answer 1

liuyubobobo 2020-04-19 21:55:49

不可以。如果你这么说，初始调用直接调用 query(0, qL, qR, qL, qR) 就好了，而不需要调用 query(0, 0, n - 1, qL, qR)。

这里的关键在于，我们要使用 l 和 r 两个参数，表示 treeIndex 这个节点所对应的区间。而线段树的这些节点代表的区间，是 mid + 1, r 或者 l，mid 的区间，直接找 qL, r 或者 l, qR，是没有对应的相应的线段树的节点的。

我们构建线段树的方式，每个节点隐含了它所对应的区间。所以，treeIndex = 0 对应了 [0, n - 1] 这个区间；每个 rightTreeIndex 对应了 [mid + 1, r] 这个区间；每个 leftTreeIndex 对应了 [l, mid] 这个区间。你可以想象成，如果我们真的把整棵线段树用 node 建立起来的话，每个 node 要包含一个区间信息的，这个区间信息就是 l, r 这两个参数的意思。只不过，在我们实现中，发现这个区间其实可以不存，在查询过程中，直接算一下就好。

继续加油！：）

Answer 2

那月真美 2020-07-17 18:21:20

同学，你没有理解这第二个参数和第三个的意义啊，这两个参数代表的是第一个参数这个节点所代表的区间的左右下标，也就是说第一个参数固定了，第二三个参数就固定不变了，跟后面的查询参数无关