Реализация дерева отрезков на пайтоне

@gordei1 · Регистрация: 22.10.2023

Студворк — интернет-сервис помощи студентам

Подскажите источники, где можно почитать про всевозможные реализации дерева отрезков на пайтоне для решения разных задач.
Неважно что это: книга или какой-то сайт и т.п.

@gordei1 · 24.10.2023, 13:21 **[ТС]**

Red white socks, я меняю его на противоположный, потому что там xor с 1 будет. А 1^1=0 0^1=1. То что надо применить xor это додумал я, изначально там было написано: поменять 1 на 0 и поменять 0 на 1 на отрезке.
Далее про сумму: спускаюсь в лист и добавляю к элементу число. И так по всему отрезку.

@iSmokeJC · 24.10.2023, 13:25

Сообщение от gordei1

поменять 1 на 0 и поменять 0 на 1

not
Не?

@Red white socks · 24.10.2023, 13:27

Сообщение от gordei1

То что надо применить xor это додумал я, изначально там было написано: поменять 1 на 0 и поменять 0 на 1 на отрезке

Ну наконец-то прояснилось. xor бинарная операция, применение ее к массиву можно интерпретировать только как вычисление кумуляты, но никак не изменение самих элементов.
Сказали бы применить отрицание, а еще лучше инверсию элементов, таких проблем с пониманием не было

@gordei1 · 24.10.2023, 13:40 **[ТС]**

Red white socks, Тогда извините за путаницу. Можете помочь исправить код пожалуйста

@Red white socks · 24.10.2023, 13:48

Теперь такой момент. Вы понимаете, что с деревом со 100М числами питон не справится ни при каком раскладе ни за 7 секунд ни за минуту?

@gordei1 · 24.10.2023, 14:50 **[ТС]**

Red white socks, да, но чисел уже не 10**8, условие изменили, я просто скопировал старое. n<=10**5 думаю с таким он должен справиться, правда кол-во запросов тоже 10**5

Добавлено через 49 минут
Red white socks кстати ещё интересно, зависит ли скорость работы дерева от того, описано оно в классе или нет

Новые блоги и статьи Все статьи Все блоги /
попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .

@gordei1 0 / 0 / 0 Регистрация: 22.10.2023 Сообщений: 26

	Реализация дерева отрезков на пайтоне 23.10.2023, 09:45. Показов 3354. Ответов 25 Метки python, segment tree, документация (Все метки) Подскажите источники, где можно почитать про всевозможные реализации дерева отрезков на пайтоне для решения разных задач. Неважно что это: книга или какой-то сайт и т.п. 0

@gordei1 0 / 0 / 0 Регистрация: 22.10.2023 Сообщений: 26
	24.10.2023, 13:21 [ТС]
	Red white socks, я меняю его на противоположный, потому что там xor с 1 будет. А 1^1=0 0^1=1. То что надо применить xor это додумал я, изначально там было написано: поменять 1 на 0 и поменять 0 на 1 на отрезке. Далее про сумму: спускаюсь в лист и добавляю к элементу число. И так по всему отрезку. 0

@gordei1 0 / 0 / 0 Регистрация: 22.10.2023 Сообщений: 26
	24.10.2023, 13:40 [ТС]
	Red white socks, Тогда извините за путаницу. Можете помочь исправить код пожалуйста 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	24.10.2023, 13:48
	Теперь такой момент. Вы понимаете, что с деревом со 100М числами питон не справится ни при каком раскладе ни за 7 секунд ни за минуту? 0

@gordei1 0 / 0 / 0 Регистрация: 22.10.2023 Сообщений: 26
	24.10.2023, 14:50 [ТС]
	Red white socks, да, но чисел уже не 108, условие изменили, я просто скопировал старое. n<=105 думаю с таким он должен справиться, правда кол-во запросов тоже 10*5 Добавлено через 49 минут* Red white socks кстати ещё интересно, зависит ли скорость работы дерева от того, описано оно в классе или нет 0

Опции темы