- дерево отрезков
- 3 Ответ от NotImplemented 2011-09-21 20:19:14 Отредактировано NotImplemented (2011-09-22 20:12:30)
- Re: дерево отрезков
- Сообщений [ 3 ]
- задача на дерево отрезков
- 2 Ответ от KADR 2010-04-21 20:04:15 Отредактировано KADR (2010-04-22 15:41:15)
- Re: задача на дерево отрезков
- Дерево отрезков — память
- 2 Ответ от Oleg 2010-10-11 11:53:37
- Re: Дерево отрезков — память
- задача на дерево отрезков
- 2 Ответ от KADR 2010-04-21 20:04:15 Отредактировано KADR (2010-04-22 15:41:15)
- Re: задача на дерево отрезков
- Дерево отрезков (изменение на отрезке)
- 2 Ответ от NotImplemented 2010-09-08 21:58:58
- Re: Дерево отрезков (изменение на отрезке)
- 3 Ответ от vanla 2011-02-07 19:41:47
- Re: Дерево отрезков (изменение на отрезке)
- 4 Ответ от Zayakin_Andrey 2011-02-07 20:49:57
- Re: Дерево отрезков (изменение на отрезке)
- 5 Ответ от e-maxx 2011-02-20 17:58:01
- Re: Дерево отрезков (изменение на отрезке)
дерево отрезков
Обновить — в плане увеличить или сделать равными икс?
Если увеличить, то для каждого отрезка нужно помимо минимума хранить еще на сколько мы все числа из отрезка увеличивали. Обновление будет выглядеть примерно так:
void update(int l,int r,int a,int b,int val,int num) < if (l==a && b==r-1) < mod[num]+=val; return; >int xx=(r+l)/2; if (b=xx) update(xx,r,a,b,val,num*2+1); else < update(l,xx,a,xx-1,val,num*2); update(xx,r,xx,b,val,num*2+1); >mn[num]=min(mn[num*2]+mod[num*2],mn[num*2+1]+mod[num*2+1]); > ll fnd(int l,int r,int a,int b,int num) < if (l==a && b==r-1) return mn[num]+mod[num]; int xx=(r+l)/2; if (b=xx) return fnd(xx,r,a,b,num*2+1)+mod[num]; else return min(fnd(l,xx,a,xx-1,num*2),fnd(xx,r,xx,b,num*2+1))+mod[num]; > Если же имелось ввиду установить равными иксу, то нужно хранить, одинаковые ли значения на данном отрезке и если одинаковые то чему они равны. При запросе просто проталкивать эту информацию к потомкам.
3 Ответ от NotImplemented 2011-09-21 20:19:14 Отредактировано NotImplemented (2011-09-22 20:12:30)
Re: дерево отрезков
Вопрос снова приобрел актуальность. Возможна ли модификация на прямоугольнике за O(logN*logN) и дополнительной памяти O(N*N)?
Сообщений [ 3 ]
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Источник
задача на дерево отрезков
Манхэттенское расстояние
На плоскости дано N различных точек. Расстоянием между точками (x1, y1) и (x2, y2) будем
считать |x1 — x2| + |y1 — y2|. Для каждой точки требуется найти одну из ближайших к ней точек.
Формат входных данных
Первая строка входного файла содержит целое число N (1 < N ). Следующие N строк
содержат по два числа — координаты точек. Координаты — целые числа, по модулю не
превышающие 10000. Числа в строках разделены пробелами.
Формат выходных данных
Выходной файл должен содержать N целых чисел, разделенных пробелом: i-е число есть номер
одной из точек, ближайших к i-й. Точки нумеруются в том порядке, в котором они даны во
входном файле, начиная с единицы.
2 Ответ от KADR 2010-04-21 20:04:15 Отредактировано KADR (2010-04-22 15:41:15)
Re: задача на дерево отрезков
Для каждой точки найдем ближайшую к ней которая лежит левее ее либо имеет ту же икс координату, но лежит ниже. Очевидно что дальше для каждой точки легко найти ближайшую среди всех остальных.
Отсортируем точки лексикографически (т.е. по икс координате, а при равных иксах по игрекам). Пусть на i-м шагу мы рассматриваем точку с координатами (x,y). Найдем для нее ближайшую точку (x’,y’).
|x-x’|+|y-y’| — минимально
x>=x’, поэтому первый модуль можно убрать
x-x’+|y-y’| — минимально
Теперь рассмотрим 2 случая:
1) y’Тогда второй модуль раскроется со знаком + и получим
x-x’+y-y’=(x+y)-(x’+y’) — минимально
Значит, нам нужно максимизировать (x’+y’).
Заведем дерево отрезков по игрекам, где для каждого игрека будем хранить максимальное значение (x’+y’) среди точек с таким игреком, которые мы уже добавили в дерево. Тогда чтобы максимизировать (x’+y’) надо просто найти максимум среди точек с игреками [-10000,y].
2) y’>y
Второй модуль раскроется со знаком минус. Тогда имеем:
x-x’+y’-y=(x-y)-(x’-y’) — минимально
Опять таки, нам нужно максимизировать (x’-y’). Заведем второе дерево отрезков и будем хранить в нем величины (x’-y’). Отвечать на запросы будем так же как и в первом случае.
Теперь просто из двух найденных точек выберем ту, которая ближе. Далее обновим оба дерева отрезков (добавим текущую точку) и перейдем к следующей. Сложность O(NlogR+NlogN), где R — макс. y координата. Если бы координаты могли быть большими, то имело бы смысл сделать сжатие координат и тогда сложность была бы просто O(NlogN).
Источник
Дерево отрезков — память
Хм. помоему не 4n а 2n-1 вершин должно быть. все вершины кроме листьев — разделяют элементы — их столько же сколько можно поставить перегородок между n элементами = n-1. ну и плюс листья — n штук. если еще для удобства добавить нулевой элемент — будет 2n.
Более того опыт показывает (http://e-maxx.ru/algo/segment_tree — скопировал просто отсюда код и потестил) что половина массива t — нули. даже если n = (2^k)+1. получается не полное двоичное дерево.. в чем нет ничего плохого при такой реализации (если делим пополам массив нечетной длины то «большая половина» будет левой частью).
2 Ответ от Oleg 2010-10-11 11:53:37
Re: Дерево отрезков — память
4n действительно грубовато но и 2n мало.
тут надо 2 * (min k такое что 2^k >= n)
например для стандартного N int t[1
А вообще пора http://e-maxx.ru/algo/segment_tree переписывать Когда дерево выровнено по 2^k все намного удобнее — можно легко определить за какой сегмент t[ i ] отвечает, легче делать Update и Build — без рекурсии.
template struct SegmentTree < SegmentTree(const T* begin, const T* end) < int sz = end - begin; Create(sz); copy(begin, end, values + dx); for (int i = dx - 1; i >= 1; i--) < values[i] = values[i * 2] + values[i * 2 + 1]; >> SegmentTree(int sz) < Create(sz); >void Create(int sz) < dx = 1; while (dx < sz) dx *= 2; values = new T[dx * 2]; memset(values, 0, sizeof(T) * dx * 2); >~SegmentTree() < delete[] values; >void Update(int pos, T value) < pos += dx; values[pos] = value; while (pos >1) < pos /= 2; values[pos] = values[pos * 2] + values[pos * 2 + 1]; >> T GetSegment(int l, int r, int pos, int tl, int tr) < if (l == tl && r == tr) return values[pos]; int m = (tl + tr) / 2; if (r = m) return GetSegment (l, r, pos * 2 + 1, m, tr); return GetSegment (l, m, pos * 2, tl, m) + GetSegment (m, r, pos * 2 + 1, m, tr); > T GetSegment(int l, int r) < return GetSegment(l, r, 1, 0, dx); >T* values; int dx; >; int a[] = ; SegmentTree tree(a, a + 4); int res = tree.GetSegment(0, 4); // r - как и в stl указывает на следующий за последним. Источник
задача на дерево отрезков
Манхэттенское расстояние
На плоскости дано N различных точек. Расстоянием между точками (x1, y1) и (x2, y2) будем
считать |x1 — x2| + |y1 — y2|. Для каждой точки требуется найти одну из ближайших к ней точек.
Формат входных данных
Первая строка входного файла содержит целое число N (1 < N ). Следующие N строк
содержат по два числа — координаты точек. Координаты — целые числа, по модулю не
превышающие 10000. Числа в строках разделены пробелами.
Формат выходных данных
Выходной файл должен содержать N целых чисел, разделенных пробелом: i-е число есть номер
одной из точек, ближайших к i-й. Точки нумеруются в том порядке, в котором они даны во
входном файле, начиная с единицы.
2 Ответ от KADR 2010-04-21 20:04:15 Отредактировано KADR (2010-04-22 15:41:15)
Re: задача на дерево отрезков
Для каждой точки найдем ближайшую к ней которая лежит левее ее либо имеет ту же икс координату, но лежит ниже. Очевидно что дальше для каждой точки легко найти ближайшую среди всех остальных.
Отсортируем точки лексикографически (т.е. по икс координате, а при равных иксах по игрекам). Пусть на i-м шагу мы рассматриваем точку с координатами (x,y). Найдем для нее ближайшую точку (x’,y’).
|x-x’|+|y-y’| — минимально
x>=x’, поэтому первый модуль можно убрать
x-x’+|y-y’| — минимально
Теперь рассмотрим 2 случая:
1) y’Тогда второй модуль раскроется со знаком + и получим
x-x’+y-y’=(x+y)-(x’+y’) — минимально
Значит, нам нужно максимизировать (x’+y’).
Заведем дерево отрезков по игрекам, где для каждого игрека будем хранить максимальное значение (x’+y’) среди точек с таким игреком, которые мы уже добавили в дерево. Тогда чтобы максимизировать (x’+y’) надо просто найти максимум среди точек с игреками [-10000,y].
2) y’>y
Второй модуль раскроется со знаком минус. Тогда имеем:
x-x’+y’-y=(x-y)-(x’-y’) — минимально
Опять таки, нам нужно максимизировать (x’-y’). Заведем второе дерево отрезков и будем хранить в нем величины (x’-y’). Отвечать на запросы будем так же как и в первом случае.
Теперь просто из двух найденных точек выберем ту, которая ближе. Далее обновим оба дерева отрезков (добавим текущую точку) и перейдем к следующей. Сложность O(NlogR+NlogN), где R — макс. y координата. Если бы координаты могли быть большими, то имело бы смысл сделать сжатие координат и тогда сложность была бы просто O(NlogN).
Источник
Дерево отрезков (изменение на отрезке)
А при выполнении операции изменения на отрезке мы будем спускаться по дереву, как в вышеописанном алгоритме суммирования, и если в какой-то момент L и R совпали с границами текущего отрезка, то мы присвоим Val[ i ] новое значение, которое мы хотим записать.
А если не совпали? Видимо, надо посмотреть, стоит ли в данной вершине Val [ i ], и если стоит, то снять и раздать детям (всё-таки, это не так очевидно 😉 ).
2 Ответ от NotImplemented 2010-09-08 21:58:58
Re: Дерево отрезков (изменение на отрезке)
Да. В дополнительном массиве можно использовать два зарезервированных значения. Первое — взять значение из суммы на отрезке [l,r], второе — продолжать спуск ниже.
struct segment_tree < int n; std::vectordata; std::vector values; std::vector etalon; segment_tree(const std::vector& array) < etalon = array; // DEBUG n = 1; while(n < (int)array.size()) n 0; --i) data[i] = data[2*i] + data[2*i+1]; > void test(int block) < std::cout ; sprintf(buf, "%02d", t); if (sum != sum_etalon) std::cout > std::cout int get_sum_etalon(int l, int r) < int sum_etalon = 0; for(int k = l; k int get_sum(int l, int r) < return get_sum(1, 0, n-1, l, r); >int get_sum(int root, int left, int right, int l, int r) < if (values[root] >0) return values[root]*(r-l+1); if (l == left && r == right && values[root] != -1) return data[root]; int sum = 0; int right_dash = (right+left)/2, left_dash = (right+left)/2+1; if (l <= right_dash) sum += get_sum(root*2, left, right_dash, l, std::min(r, right_dash) ); if (r >= left_dash) sum += get_sum(root*2+1, left_dash, right, std::max(left_dash, l), r); return sum; > void set_value(int l, int r, int value) < set_value_etalon(l, r, value); set_value(1, 0, n-1, l, r, value); >void set_value_etalon(int l, int r, int value) < for(int k = l; k void set_value(int root, int left, int right, int l, int r, int value) < if (l == left && r == right) < values[root] = value; return; >if (values[root] > 0) values[root*2 + 1] = values[root*2] = values[root]; values[root] = -1; int right_dash = (right+left)/2, left_dash = (right+left)/2+1; if (l <= right_dash) set_value(root*2, left, right_dash, l, std::min(r, right_dash), value); if (r >= left_dash) set_value(root*2+1, left_dash, right, std::max(left_dash, l), r, value); > >; int main(int argc, char* argv[]) < int data[] = ; std::vector arr(data, data+sizeof(data)/sizeof(data[0])); segment_tree st(arr); int t = 1; st.test(t++); st.set_value(0, 6, 4); st.test(t++); st.set_value(1, 4, 6); st.test(t++); st.set_value(2, 8, 5); st.test(t++); >3 Ответ от vanla 2011-02-07 19:41:47
Re: Дерево отрезков (изменение на отрезке)
Кстати, мне не очень понятно, почему размер массива должен быть в 4 раза больше количества элементов. Ведь, кажется, из самого построения алгоритма видно, что вершин в дереве 2n — 1. В чем я неправ?
4 Ответ от Zayakin_Andrey 2011-02-07 20:49:57
Re: Дерево отрезков (изменение на отрезке)
Кстати, мне не очень понятно, почему размер массива должен быть в 4 раза больше количества элементов. Ведь, кажется, из самого построения алгоритма видно, что вершин в дереве 2n — 1. В чем я неправ?
В лучшем случае будет нужно 2n-1 памяти — когда размер исходного массива степень двойки, вот представьте полное бинарное дерево, и посчитайте сколько оно будет занимать памяти. Если же размер не степень двойки, то размер исходного массива дополняют до степени — отсюда и такая оценка.
5 Ответ от e-maxx 2011-02-20 17:58:01
Re: Дерево отрезков (изменение на отрезке)
В новой версии статьи постарался покрыть все эти вопросы. Жду ещё конструктивных замечаний
Источник