編集: 私は spoj 問題を解決しようとしていました。問題へのリンクは次のとおりです。 http://spoj.pl/problems/BRCKTS
問題を解決するための 2 つの可能なデータ構造を考えることができます。1 つはセグメント ツリーを使用し、もう 1 つは BIT を使用します。セグメント ツリーを使用してソリューションを既に実装しています。BIT について読んだことがありますが、それを使って特定のことを行う方法がわかりません (以下で説明します)。
(のみまたはのみを含む特定の文字列で括弧のバランスが取れているかどうかを確認しようとしています)。問題を解決するためにBIT（バイナリインデックスツリー）を使用しています。私が従う手順は次のとおりです。
文字列の文字数と同じサイズの配列を取得しています。対応する配列要素に-1 for)と 1 forを割り当てています。(
次の 2 つの条件が true の場合にのみ、ブラケットは文字列内でバランスが取れています。
- 配列全体の累積合計はゼロです。
- 最小累積合計は負ではありません。つまり、配列のすべてのプレフィックスの累積合計の最小値は負ではありません。
BIT を使用して条件 1 をチェックするのは簡単です。条件2のチェックで問題に直面しています。