Соответствие скобок с помощью BIT

Редактировать: я пытался решить проблему спой. Вот ссылка на проблему: http://spoj.pl/problems/BRCKTS

Я могу думать о двух возможных структурах данных для решения проблемы: одна использует дерево сегментов, а другая - BIT. Я уже реализовал решение с использованием дерева сегментов. Я читал о BIT, но я не могу понять, как сделать с ним определенную вещь (о которой я упоминал ниже)

Я пытаюсь проверить, сбалансированы ли скобки в заданной строке, содержащей только (или )"S. Я использую BIT(Binary indexed tree) для решения проблемы. Я придерживаюсь следующей процедуры:

Я беру массив размером, равным количеству символов в строке. Я назначаю -1 для ) и 1 для ( в соответствующие элементы массива.

Скобки в строке сбалансированы, только если выполняются следующие два условия.

  • Накопленная сумма всего массива равна нулю.
  • Минимальная накопленная сумма не является отрицательной. т.е. минимум кумулятивных сумм всех префиксов массива неотрицателен.

Проверка условия 1 с использованием BIT тривиальна. Я столкнулся с проблемой при проверке условия 2.

Источник

1 ответ

Решение

Вот очень хорошее руководство по бинарным индексированным деревьям: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees а вот более прямое, но менее полное: http://programmersdream.com/data -структуры / двоично-индексированных дерево /

Источник
Другие вопросы по тегам