c++ - 段树的迭代代码

Question

我想在 C++ 中编写段树代码并通过递归编写代码查询操作，但它很慢并且给出了 TLE。因此，有人可以通过迭代建议和解释以下代码，这将是一个很大的帮助。提前致谢。

以下代码在一个范围内计算 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 -segment 开始

se段结束

index - 段树的当前节点

L - 查询下界

R - 上界

Answer 1

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

Answer 2

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