Итерационный код для дерева сегментов
Я хотел закодировать дерево сегментов в 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-Сегмент Дерево
сс-Начало сегмента
се-конец сегмента
индекс-текущий узел дерева сегментов
L-Нижняя граница запроса
р-верхняя граница
Решение
Вы передаете вектор по значению. Он копируется каждый раз, когда вы вызываете эту функцию. Таким образом, временная сложность вашего решения составляет O (n * log n) на запрос, а не O (log n). Передача вектора по ссылке должна исправить это.
Другие решения