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 -セグメント開始

seセグメントの終わり

index - セグメント ツリーの現在のノード

L -クエリ境界の下限

R上限

Answer 1

ベクトルを値で渡します。この関数を呼び出すたびにコピーされます。したがって、ソリューションの時間の複雑さは、クエリごとに O(n * log n) であり、O(log n) ではありません。ベクトルを参照で渡すと修正されます。

Answer 2

本当に繰り返し実行したい場合は、それがただの DFS に何か特別なものがあることに注意してください。スタックを使用して反復 DFS を簡単に実行できます。