edit: я пытался решить проблему спой. Вот ссылка на проблему:
http://spoj.pl/problems/BRCKTS
Я могу придумать две возможные структуры данных для решения проблемы: одну с использованием дерева сегментов, а другую с помощью BIT.
Я уже реализовал решение с использованием дерева сегментов. Я читал о BIT, но я не могу понять, как сделать с ним определенную вещь (о которой я упоминал ниже)
Я пытаюсь проверить, сбалансированы ли скобки в заданной строке, содержащей только ( или ).
Я использую BIT (Binary indexed tree) для решения проблемы.
Я придерживаюсь следующей процедуры:
Я беру массив размером, равным количеству символов в строке.
Я присваиваю -1 для ) и 1 для ( для соответствующих элементов массива.
Скобки в строке сбалансированы, только если выполняются следующие два условия.
- Совокупная сумма всего массива равна нулю.
- Минимальная накопленная сумма не является отрицательной.
т.е. минимальная сумма кумулятивных сумм всех префиксов массива неотрицательна.
Проверка условия 1 с использованием BIT тривиальна.
Я столкнулся с проблемой при проверке условия 2.