[内容有误] 线段树查询中值计算错误

[h1542462994]

请选择：

• 我正在着手修复这个问题

我正在访问这个页面

https://oi-wiki.org/ds/seg/#%E7%BA%BF%E6%AE%B5%E6%A0%91%E7%9A%84%E5%8C%BA%E9%97%B4%E6%9F%A5%E8%AF%A2

我发现页面有这样的问题

int getsum(int l, int r, int s, int t, int p) {
  // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
  if (l <= s && t <= r)
    return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
  int m = s + ((t - s) >> 1), sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
  return sum;
}

在上述函数中，该处出现错误

  int m = s + ((t - s) >> 1);

我们以10个元素举例，此时s=1，t=10，作图可得m=6。带入上式，可以得到m=5，与预期不符，出现错误。
出现此问题的原因是线段树不是一个完全二叉树，不可以直接计算得出中值。

[welcome]

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～

[HeRaNO]

是按什么原则画图的？是左闭右开还是左闭右闭？这里线段树建树是左闭右闭的。按理说 $[1,10]$ 这个区间，是应该 $m=5$ 分成 $[1,5]$ 和 $[6,10]$ 两个区间吧，这样左右区间长度是等长的。如果考虑 $m=6$ 按左闭右闭区间建树，左右子树区间长度差就大于 $1$ 了？

[h1542462994]

是按什么原则画图的？是左闭右开还是左闭右闭？这里线段树建树是左闭右闭的。按理说 [1,10] 这个区间，是应该 m=5 分成 [1,5] 和 [6,10] 两个区间吧，这样左右区间长度是等长的。如果考虑 m=6 按左闭右闭区间建树，左右子树区间长度差就大于 1 了？

我使用非递归的方式从后往前建非完全二叉树的，我又看了一下wiki里面是用递归方式建平衡树的，所有会出现长度差>1的情况。wiki里面应该是没错的，是我理解出现了偏差。