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