括弧列区間クエリ (DataStructure/bracket_range_query.hpp)
- View this file on GitHub
- View document part on GitHub
- Last update: 2026-01-18 20:01:55+09:00
- Include:
#include "DataStructure/bracket_range_query.hpp"
括弧列区間クエリ
文字列に対して1点更新と区間が正しい括弧列として成立するかの判定を行うデータ構造です。
判定では '(' と ')' 以外の文字は無視します。
-
set(i, c):i文字目をcに変更 -
is_valid(l, r): 区間[l, r)の部分文字列から'('と')'だけを抜き出した列が、正しい括弧列か判定
コンストラクタ
BracketRangeQuery(const std::string& s)
初期文字列 s で初期化します。
制約
-
sは任意の文字列でよい（ただし判定に寄与するのは'('と')'のみ）
計算量
- $O(|s|)$
BracketRangeQuery(int N)
長さ N の文字列で初期化します。初期状態はすべて「括弧以外」（寄与 0）として扱います。
制約
- $0 \leq N$
計算量
- $O(N)$
set
void set(int i, char c)
i 文字目（0-indexed）を c に変更します。
c が '(' / ')' 以外の場合は、判定上は「無視される文字」として扱われます。
制約
0 ≤ i < N-
cは任意の文字でよい（ただし判定に寄与するのは'('と')'のみ）
計算量
- $O(\log N)$
is_valid
bool is_valid(int l, int r)
区間 [l, r)（0-indexed）の部分文字列から '(' と ')' のみを抜き出した列が、正しい括弧列であるか判定します。
空区間（l == r）は常に true を返します。
戻り値
- 正しい括弧列なら
true - そうでなければ
false
制約
0 ≤ l ≤ r ≤ N
計算量
- $O(\log N)$
str（デバッグ用）
const std::string& str() const
内部に保持している現在の文字列を参照で返します（デバッグ用途を想定）。
計算量
- $O(1)$
関連情報
-
AtCoder Library
lazysegtree: 依存クラス
Verified with
Code
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
class BracketRangeQuery
{
using S = int;
using F = int;
static constexpr int INF = (int)1e9;
static S op(S a, S b) { return min(a, b); }
static S e() { return INF; }
static S mapping(F f, S x)
{
return x == INF ? INF : x + f;
}
static F composition(F f, F g)
{
return f + g;
}
static F id() { return 0; }
using seg_t = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
public:
BracketRangeQuery() : n(0), seg() {}
explicit BracketRangeQuery(const string &s_)
{
init(s_);
}
explicit BracketRangeQuery(int n_)
{
init(string(n_, '?'));
}
// i 文字目を c に変更
void set(int i, char c)
{
assert(0 <= i && i < n);
seg.apply(i + 1, n + 1, conv(c) - conv(s[i]));
s[i] = c;
}
// [l, r) が正しい括弧列か？
bool is_valid(int l, int r)
{
assert(0 <= l && l <= r && r <= n);
int base = seg.get(l);
int right = seg.get(r);
if (right - base != 0)
return false;
if (l == r)
return true;
int mn = seg.prod(l + 1, r + 1);
return mn >= base;
}
const string &str() const { return s; }
private:
int n;
string s;
seg_t seg;
static int conv(char c)
{
if (c == '(')
return +1;
if (c == ')')
return -1;
return 0; // 括弧以外は寄与なし
}
void init(const string &s_)
{
s = s_;
n = (int)s.size();
vector<S> pref(n + 1);
pref[0] = 0;
for (int i = 0; i < n; ++i)
{
pref[i + 1] = pref[i] + conv(s[i]);
}
seg = seg_t(pref);
}
};#line 1 "DataStructure/bracket_range_query.hpp"
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
class BracketRangeQuery
{
using S = int;
using F = int;
static constexpr int INF = (int)1e9;
static S op(S a, S b) { return min(a, b); }
static S e() { return INF; }
static S mapping(F f, S x)
{
return x == INF ? INF : x + f;
}
static F composition(F f, F g)
{
return f + g;
}
static F id() { return 0; }
using seg_t = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
public:
BracketRangeQuery() : n(0), seg() {}
explicit BracketRangeQuery(const string &s_)
{
init(s_);
}
explicit BracketRangeQuery(int n_)
{
init(string(n_, '?'));
}
// i 文字目を c に変更
void set(int i, char c)
{
assert(0 <= i && i < n);
seg.apply(i + 1, n + 1, conv(c) - conv(s[i]));
s[i] = c;
}
// [l, r) が正しい括弧列か？
bool is_valid(int l, int r)
{
assert(0 <= l && l <= r && r <= n);
int base = seg.get(l);
int right = seg.get(r);
if (right - base != 0)
return false;
if (l == r)
return true;
int mn = seg.prod(l + 1, r + 1);
return mn >= base;
}
const string &str() const { return s; }
private:
int n;
string s;
seg_t seg;
static int conv(char c)
{
if (c == '(')
return +1;
if (c == ')')
return -1;
return 0; // 括弧以外は寄与なし
}
void init(const string &s_)
{
s = s_;
n = (int)s.size();
vector<S> pref(n + 1);
pref[0] = 0;
for (int i = 0; i < n; ++i)
{
pref[i + 1] = pref[i] + conv(s[i]);
}
seg = seg_t(pref);
}
};