线段树的迭代代码

Question

我想用 C++ 编写线段树代码，并通过递归编写代码查询操作，但它很慢并且会产生 TLE。因此，有人可以建议并解释通过迭代编写以下代码，这将是一个很好的 help.Thanks 提前。

以下代码在一定范围内计算 gcd

int getgcd(vector<int> T, int ss,int se, int L, int R, int index)
{
if (L <= ss && R >= se)
      return T[index];
if (se < L || ss > R)
      return 0;
int mid = ((ss+se)>>1);
      return __gcd(getgcd(T, ss, mid, L, R, index<<1),getgcd(T, mid+1, se, L, R, (index<<1)+1));
}

这里，

T-段树

ss-段开始

se-段结束

index-线段树的当前节点

L-查询下界

R-查询上限

Answer 1

您按值传递向量。每次调用此函数时都会复制它。因此，您的解决方案的时间复杂度是每个查询 O(n * log n)，而不是 O(log n)。通过引用传递向量应该可以修复它。

Answer 2

如果你真的想迭代地做它，请注意它只是一个带有额外内容的 DFS。您可以使用堆栈轻松执行迭代 DFS。

线段树的迭代代码

Iterative code for segment tree

c++

algorithm

segment-tree