Обсуждение:Дерево отрезков. Построение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «: {{tick}} Неправда, не только сумму и минимум. Вообще здесь на лекции вроде говорили про монои...»)
 
 
(не показано 6 промежуточных версий 4 участников)
Строка 1: Строка 1:
−
: {{tick}} Неправда, не только сумму и минимум. Вообще здесь на лекции вроде говорили про моноид, надо добавить.
+
: {{tick|ticked=1}} Неправда, не только сумму и минимум. Вообще здесь на лекции вроде говорили про моноид, надо добавить.
−
: {{tick}} "разрешается присвоить всем элементам  какое-либо значение, либо прибавить ко всем элементам массива какое-либо число" Опять же, не только это. Тут, кажется, было дз как расширить понятие моноида и на такие операции.
+
:: Зачем все так усложнять? -[[Участник:Demid.Kucherenko|Demid.Kucherenko]] 19:02, 13 мая 2012 (GST)
−
: {{tick}}  "Пустые элементы можно заполнить нулями или бесконечностями" видимо, нейтральными элементами тогда уж.
+
::: Да, усложнять. Затем, что этим усложнением достигается больший формализм, который тут вполне уместен. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 15:59, 15 мая 2012 (GST)
−
: {{tick}} Мне кажется, лучше сделать так, чтобы мы работали с полуинтервалами( [left, right) ). Иначе обычно начинаются проблемы с реализацией.  
+
:::: {{tick|ticked=1}} Надо либо дать ссылку на определение моноида, если оно есть на вики-конспектах, либо добавить его сюда. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 10:54, 16 мая 2012 (GST)
−
: {{tick}} написать, что такое построение снизу, построение сверху.
+
: {{tick|ticked=1}} "разрешается присвоить всем элементам  какое-либо значение, либо прибавить ко всем элементам массива какое-либо число" Опять же, не только это. Тут, кажется, было дз как расширить понятие моноида и на такие операции.
−
: {{tick}} категории --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:06, 7 февраля 2012 (MSK)
+
:: Понятно, что не только это, но все зависит от конкретной задачи, а наиболее используемые свойства здесь перечислены, остальное во многом экзотика -[[Участник:Demid.Kucherenko|Demid.Kucherenko]] 19:02, 13 мая 2012 (GST)
 +
::: очень многое, что нам рассказывают — какая-то вроде экзотика и абстрактный треш, тем не менее, оно используется. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 15:59, 15 мая 2012 (GST)
 +
:::: У нас такого дз не было, проверил -[[Служебная:Contributions/194.85.160.133|194.85.160.133]] 16:56, 15 мая 2012 (GST)
 +
::::: ок. тогда хотя бы дай ссылку на конспект про массовые операции. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 10:54, 16 мая 2012 (GST)
 +
::::: и перед «т.е. разрешается присвоить всем элементам  какое-либо значение, либо прибавить ко всем элементам массива какое-либо число.» должно быть слово «например»
 +
: {{tick | ticked=1}}  "Пустые элементы можно заполнить нулями или бесконечностями" видимо, нейтральными элементами тогда уж.
 +
:: Если писать через моноиды то да, но я считаю это запутывающим -[[Участник:Demid.Kucherenko|Demid.Kucherenko]] 19:02, 13 мая 2012 (GST)
 +
::: Как раз таки это не запутывание. Запутывание — это когда ты не понимаешь, к каким операциям можно применить дерево отрезков, к каким нет, и как этого все-таки добиться. Если написать про моноид, человек, который поймет это, поймет это полностью.
 +
: {{tick | ticked=1}} Мне кажется, лучше сделать так, чтобы мы работали с полуинтервалами( [left, right) ). Иначе обычно начинаются проблемы с реализацией.  
 +
: {{tick|ticked=1}} написать, что такое построение снизу, построение сверху.
 +
:: {{tick | ticked=1}}как-то совсем мутно написано. И можно хотя бы ссылки на статьи сделать.
 +
:: {{tick|ticked=1}} упоминание динамики по дереву, имхо, тут лишнее, это обычная такая рекурсия же.
 +
: {{tick | ticked=1}} псевдокод
 +
:: {{tick|ticked=1}} В описании все еще корень в 0, 2*i и 2*i+1 и все такое.
 +
:: {{tick | ticked=1}} Обычно у нас 0-индексация, так что 2*i и 2*i + 1 не работают. И опять же, надо не RSQ, а абстрактную функцию
 +
: {{tick | ticked=1}} категории --[[Участник:Dgerasimov|Дмитрий Герасимов]] 00:06, 7 февраля 2012 (MSK)
 +
: {{tick}} «Далее будем считать, что дерево выстраиваем для задачи вычисления суммы на отрезке. Для минимума и максимума операция построения проделывается аналогично.» — видимо, это уже не так.
 +
: {{tick | ticked=1}} «Создадим функцию от исходного массива a...» — звучит как-то бредово.
 +
: {{tick | ticked=1}} «т.е. родитель являлся бы суммой своих сыновей» — не суммой, а значением функции от них.
 +
: {{tick | ticked=1}} «Лучше всего эту процедуру делать рекурсивно» — не лучше всего, а один из вариантов.
 +
: {{tick}} надо, наверное, сначала написать про виды построения и запросов на дереве отрезков (сверху/снизу), а потом уже описывать их. Кстати, по ссылкам только реализация запроса, а построения снизу нет, так что его тоже надо описать.
 +
:: Сначала напиши про виды построения, а потом уже описывай их. И построение снизу опиши подробнее, добавь псевдокод. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 17:43, 26 мая 2012 (GST)

Текущая версия на 16:43, 26 мая 2012

☑ Неправда, не только сумму и минимум. Вообще здесь на лекции вроде говорили про моноид, надо добавить.
Зачем все так усложнять? -Demid.Kucherenko 19:02, 13 мая 2012 (GST)
Да, усложнять. Затем, что этим усложнением достигается больший формализм, который тут вполне уместен. --Дмитрий Герасимов 15:59, 15 мая 2012 (GST)
☑ Надо либо дать ссылку на определение моноида, если оно есть на вики-конспектах, либо добавить его сюда. --Дмитрий Герасимов 10:54, 16 мая 2012 (GST)
☑ "разрешается присвоить всем элементам какое-либо значение, либо прибавить ко всем элементам массива какое-либо число" Опять же, не только это. Тут, кажется, было дз как расширить понятие моноида и на такие операции.
Понятно, что не только это, но все зависит от конкретной задачи, а наиболее используемые свойства здесь перечислены, остальное во многом экзотика -Demid.Kucherenko 19:02, 13 мая 2012 (GST)
очень многое, что нам рассказывают — какая-то вроде экзотика и абстрактный треш, тем не менее, оно используется. --Дмитрий Герасимов 15:59, 15 мая 2012 (GST)
У нас такого дз не было, проверил -194.85.160.133 16:56, 15 мая 2012 (GST)
ок. тогда хотя бы дай ссылку на конспект про массовые операции. --Дмитрий Герасимов 10:54, 16 мая 2012 (GST)
и перед «т.е. разрешается присвоить всем элементам какое-либо значение, либо прибавить ко всем элементам массива какое-либо число.» должно быть слово «например»
☑ "Пустые элементы можно заполнить нулями или бесконечностями" видимо, нейтральными элементами тогда уж.
Если писать через моноиды то да, но я считаю это запутывающим -Demid.Kucherenko 19:02, 13 мая 2012 (GST)
Как раз таки это не запутывание. Запутывание — это когда ты не понимаешь, к каким операциям можно применить дерево отрезков, к каким нет, и как этого все-таки добиться. Если написать про моноид, человек, который поймет это, поймет это полностью.
☑ Мне кажется, лучше сделать так, чтобы мы работали с полуинтервалами( [left, right) ). Иначе обычно начинаются проблемы с реализацией.
☑ написать, что такое построение снизу, построение сверху.
☑как-то совсем мутно написано. И можно хотя бы ссылки на статьи сделать.
☑ упоминание динамики по дереву, имхо, тут лишнее, это обычная такая рекурсия же.
☑ псевдокод
☑ В описании все еще корень в 0, 2*i и 2*i+1 и все такое.
☑ Обычно у нас 0-индексация, так что 2*i и 2*i + 1 не работают. И опять же, надо не RSQ, а абстрактную функцию
☑ категории --Дмитрий Герасимов 00:06, 7 февраля 2012 (MSK)
☐ «Далее будем считать, что дерево выстраиваем для задачи вычисления суммы на отрезке. Для минимума и максимума операция построения проделывается аналогично.» — видимо, это уже не так.
☑ «Создадим функцию от исходного массива a...» — звучит как-то бредово.
☑ «т.е. родитель являлся бы суммой своих сыновей» — не суммой, а значением функции от них.
☑ «Лучше всего эту процедуру делать рекурсивно» — не лучше всего, а один из вариантов.
☐ надо, наверное, сначала написать про виды построения и запросов на дереве отрезков (сверху/снизу), а потом уже описывать их. Кстати, по ссылкам только реализация запроса, а построения снизу нет, так что его тоже надо описать.
Сначала напиши про виды построения, а потом уже описывай их. И построение снизу опиши подробнее, добавь псевдокод. --Дмитрий Герасимов 17:43, 26 мая 2012 (GST)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Дерево_отрезков._Построение&oldid=22775»