Предисловие

Наверное, довольно странная идея писать дерево отрезков на python, но мне давно хотелось потренироваться в написании unit тестов и настройке CI, и, думаю, что дерево отрезков как раз идеально подходит под эту задачу.

Постановка задачи

Пусть у нас есть массив N и к нам поступает Q запросов следующего типа:

1 l r x прибавить к элементам массива N_l, N_{l + 1}, ..., N_{r - 1}, N_r число x

2 l r вывести сумму: N_l + N_{l + 1} + ... + N_{r - 1} + N_r

Пример

Тест:

5
1 2 3 4 5
4
2 0 4
1 1 3 8
1 0 2 4
2 0 4

Ответ:

15
51

Структура программы

Запуск

Для запуска программы нужно написать:

python main.py

и указать файл с тестом, например, tests/files/main_test.txt

class BaseTree

Данный класс является абстракным базовым классом, на основании уже которых создаются классы Tree и TestTree.

class Tree

У нашего класса Tree есть два метода:

• get_sum(l, r) - возвращат сумму на отрезке [l, r]
• do_update(l, r, add) - прибавляет ко всем элементам массива на отрезке [l, r] число add

class TestTree

Данный класс содержит такие же методы, как и Tree и был написан для того, чтобы получать правильные ответы и сверять их с ответами, полученными методами Tree, но за асимтотику О(len(N) * Q)

generate_test

Данная функция используется для генерации файлов с тестами. Все тесты записываются в папку tests/files

Для запуска нужно написать:

python tests/generate_test

и указать два параметра: размер массива и количество запросов к нему.

Тестирование

Для запуска тестирования нужно написать:

python tests/test.py

Также можно запустить тесты вручную с помощью github actions. Бейдж о результатах тестирования находится в самом начале данного файла.