Skip to content

Commit 035c9d2

Browse files
suisen-cpsuisen-cp
committed
SegTree & LazySegTree
1 parent f29bfec commit 035c9d2

3 files changed

Lines changed: 396 additions & 1 deletion

File tree

‎LazySegTree/LazySegTree.java‎

Lines changed: 235 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,235 @@
1+
/**
2+
* TODO: verify {@link LazySegTree#maxRight} and {@link LazySegTree#minLeft}
3+
*
4+
* @verified https://atcoder.jp/contests/practice2/tasks/practice2_k
5+
*/
6+
class LazySegTree<S, F> {
7+
final int MAX;
8+
9+
final int N;
10+
final int Log;
11+
final java.util.function.BinaryOperator<S> Op;
12+
final S E;
13+
final java.util.function.BiFunction<F, S, S> Mapping;
14+
final java.util.function.BinaryOperator<F> Composition;
15+
final F Id;
16+
17+
final S[] Dat;
18+
final F[] Laz;
19+
20+
@SuppressWarnings("unchecked")
21+
public LazySegTree(int n, java.util.function.BinaryOperator<S> op, S e, java.util.function.BiFunction<F, S, S> mapping, java.util.function.BinaryOperator<F> composition, F id) {
22+
this.MAX = n;
23+
int k = 1;
24+
while (k < n) k <<= 1;
25+
this.N = k;
26+
this.Log = Integer.numberOfTrailingZeros(N);
27+
this.Op = op;
28+
this.E = e;
29+
this.Mapping = mapping;
30+
this.Composition = composition;
31+
this.Id = id;
32+
this.Dat = (S[]) new Object[N << 1];
33+
this.Laz = (F[]) new Object[N];
34+
java.util.Arrays.fill(Dat, E);
35+
java.util.Arrays.fill(Laz, Id);
36+
}
37+
38+
public LazySegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e, java.util.function.BiFunction<F, S, S> mapping, java.util.function.BinaryOperator<F> composition, F id) {
39+
this(dat.length, op, e, mapping, composition, id);
40+
build(dat);
41+
}
42+
43+
private void build(S[] dat) {
44+
int l = dat.length;
45+
System.arraycopy(dat, 0, Dat, N, l);
46+
for (int i = N - 1; i > 0; i--) {
47+
Dat[i] = Op.apply(Dat[i << 1 | 0], Dat[i << 1 | 1]);
48+
}
49+
}
50+
51+
private void push(int k) {
52+
if (Laz[k] == Id) return;
53+
int lk = k << 1 | 0, rk = k << 1 | 1;
54+
Dat[lk] = Mapping.apply(Laz[k], Dat[lk]);
55+
Dat[rk] = Mapping.apply(Laz[k], Dat[rk]);
56+
if (lk < N) Laz[lk] = Composition.apply(Laz[k], Laz[lk]);
57+
if (rk < N) Laz[rk] = Composition.apply(Laz[k], Laz[rk]);
58+
Laz[k] = Id;
59+
}
60+
61+
private void pushTo(int k) {
62+
for (int i = Log; i > 0; i--) push(k >> i);
63+
}
64+
65+
private void pushTo(int lk, int rk) {
66+
for (int i = Log; i > 0; i--) {
67+
if (((lk >> i) << i) != lk) push(lk >> i);
68+
if (((rk >> i) << i) != rk) push(rk >> i);
69+
}
70+
}
71+
72+
private void updateFrom(int k) {
73+
k >>= 1;
74+
while (k > 0) {
75+
Dat[k] = Op.apply(Dat[k << 1 | 0], Dat[k << 1 | 1]);
76+
k >>= 1;
77+
}
78+
}
79+
80+
private void updateFrom(int lk, int rk) {
81+
for (int i = 1; i <= Log; i++) {
82+
if (((lk >> i) << i) != lk) {
83+
int lki = lk >> i;
84+
Dat[lki] = Op.apply(Dat[lki << 1 | 0], Dat[lki << 1 | 1]);
85+
}
86+
if (((rk >> i) << i) != rk) {
87+
int rki = (rk - 1) >> i;
88+
Dat[rki] = Op.apply(Dat[rki << 1 | 0], Dat[rki << 1 | 1]);
89+
}
90+
}
91+
}
92+
93+
public void set(int p, S x) {
94+
exclusiveRangeCheck(p);
95+
p += N;
96+
pushTo(p);
97+
Dat[p] = x;
98+
updateFrom(p);
99+
}
100+
101+
public S get(int p) {
102+
exclusiveRangeCheck(p);
103+
p += N;
104+
pushTo(p);
105+
return Dat[p];
106+
}
107+
108+
public S prod(int l, int r) {
109+
if (l > r) {
110+
throw new IllegalArgumentException(
111+
String.format("Invalid range: [%d, %d)", l, r)
112+
);
113+
}
114+
inclusiveRangeCheck(l);
115+
inclusiveRangeCheck(r);
116+
if (l == r) return E;
117+
l += N; r += N;
118+
pushTo(l, r);
119+
S sumLeft = E, sumRight = E;
120+
while (l < r) {
121+
if ((l & 1) == 1) sumLeft = Op.apply(sumLeft, Dat[l++]);
122+
if ((r & 1) == 1) sumRight = Op.apply(Dat[--r], sumRight);
123+
l >>= 1; r >>= 1;
124+
}
125+
return Op.apply(sumLeft, sumRight);
126+
}
127+
128+
public S allProd() {
129+
return Dat[1];
130+
}
131+
132+
public void apply(int p, F f) {
133+
Dat[p] = Mapping.apply(f, get(p));
134+
updateFrom(p + N);
135+
}
136+
137+
public void apply(int l, int r, F f) {
138+
if (l > r) {
139+
throw new IllegalArgumentException(
140+
String.format("Invalid range: [%d, %d)", l, r)
141+
);
142+
}
143+
inclusiveRangeCheck(l);
144+
inclusiveRangeCheck(r);
145+
if (l == r) return;
146+
l += N; r += N;
147+
pushTo(l, r);
148+
for (int l2 = l, r2 = r; l2 < r2;) {
149+
if ((l2 & 1) == 1) {
150+
Dat[l2] = Mapping.apply(f, Dat[l2]);
151+
if (l2 < N) Laz[l2] = Composition.apply(f, Laz[l2]);
152+
l2++;
153+
}
154+
if ((r2 & 1) == 1) {
155+
r2--;
156+
Dat[r2] = Mapping.apply(f, Dat[r2]);
157+
if (r2 < N) Laz[r2] = Composition.apply(f, Laz[r2]);
158+
}
159+
l2 >>= 1; r2 >>= 1;
160+
}
161+
updateFrom(l, r);
162+
}
163+
164+
public int maxRight(int l, java.util.function.Predicate<S> g) {
165+
inclusiveRangeCheck(l);
166+
if (!f.test(E)) {
167+
throw new IllegalArgumentException("Identity element must satisfy the condition.");
168+
}
169+
if (l == MAX) return MAX;
170+
l += N;
171+
pushTo(l);
172+
S sum = E;
173+
do {
174+
l >>= Integer.numberOfTrailingZeros(l);
175+
if (!g.test(Op.apply(sum, Dat[l]))) {
176+
while (l < N) {
177+
push(l);
178+
l = l << 1;
179+
if (g.test(Op.apply(sum, Dat[l]))) {
180+
sum = Op.apply(sum, Dat[l]);
181+
l++;
182+
}
183+
}
184+
return l - N;
185+
}
186+
sum = Op.apply(sum, Dat[l]);
187+
l++;
188+
} while ((l & -l) != l);
189+
return MAX;
190+
}
191+
192+
public int minLeft(int r, java.util.function.Predicate<S> g) {
193+
inclusiveRangeCheck(r);
194+
if (!f.test(E)) {
195+
throw new IllegalArgumentException("Identity element must satisfy the condition.");
196+
}
197+
if (r == 0) return 0;
198+
r += N;
199+
pushTo(r - 1);
200+
S sum = E;
201+
do {
202+
r--;
203+
while (r > 1 && (r & 1) == 1) r >>= 1;
204+
if (!g.test(Op.apply(Dat[r], sum))) {
205+
while (r < N) {
206+
push(r);
207+
r = r << 1 | 1;
208+
if (g.test(Op.apply(Dat[r], sum))) {
209+
sum = Op.apply(Dat[r], sum);
210+
r--;
211+
}
212+
}
213+
return r + 1 - N;
214+
}
215+
sum = Op.apply(Dat[r], sum);
216+
} while ((r & -r) != r);
217+
return 0;
218+
}
219+
220+
private void exclusiveRangeCheck(int p) {
221+
if (p < 0 || p >= MAX) {
222+
throw new IndexOutOfBoundsException(
223+
String.format("Index %d is not in [%d, %d).", p, 0, MAX)
224+
);
225+
}
226+
}
227+
228+
private void inclusiveRangeCheck(int p) {
229+
if (p < 0 || p > MAX) {
230+
throw new IndexOutOfBoundsException(
231+
String.format("Index %d is not in [%d, %d].", p, 0, MAX)
232+
);
233+
}
234+
}
235+
}

‎LazySegTree/Readme.md‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
# クラス LazySegTree
2+
3+
[モノイド](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89) `(S,⋅:S×S→S,e∈S)` と、`S` から `S` への写像の集合 `F` であって、以下の条件を満たすようなものについて使用できるデータ構造です。
4+
5+
- `F` は恒等写像 `id` を含む。つまり、任意の $x∈S$ に対し `id(x) = x` をみたす。
6+
- `F` は写像の合成について閉じている。つまり、任意の `f,g∈F` に対し `f∘g∈F` である。
7+
- 任意の `f∈F,x,y∈S` に対し `f(x⋅y)=f(x)⋅f(y)` をみたす。
8+
9+
長さ `N` の `S` の配列に対し、
10+
11+
- 区間の要素に一括で `F` の要素 `f` を作用 (`x = f(x)`)
12+
- 区間の要素の総積の取得
13+
14+
を $O(\log N)$ で行うことが出来ます。
15+
16+
また、このライブラリはオラクルとして `op`, `mapping`, `composition` を使用しますが、これらが定数時間で動くものと仮定したときの計算量を記述します。オラクル内部の計算量が $O(f(n))$ である場合はすべての計算量が $O(f(n))$ 倍となります
17+
18+
## コンストラクタ
19+
20+
引数の意味は以下の通りです
21+
22+
- `S` : モノイドの型
23+
- `F` : 写像の型
24+
- `op` : `⋅:S×S→S` を計算する関数 S
25+
- `e` : モノイドの単位元
26+
- `mapping`: `f(x)` を返す関数
27+
- `composition` : `f∘g` を返す関数
28+
- `id` : 恒等写像
29+
30+
```java
31+
public LazySegTree<S, F>(int n, java.util.function.BinaryOperator<S> op, S e, java.util.function.BiFunction<F, S, S> mapping, java.util.function.BinaryOperator<F> composition, F id)
32+
```
33+
34+
長さ `n` の配列 `a[0], a[1], ..., a[n - 1]` を作ります. 初期値はすべて $e$ です.
35+
36+
計算量: $O(n)$
37+
38+
```java
39+
public LazySegTree<S, F>(S[] dat, java.util.function.BinaryOperator<S> op, S e, java.util.function.BiFunction<F, S, S> mapping, java.util.function.BinaryOperator<F> composition, F id)
40+
```
41+
42+
長さ `n` の配列 `a[0], a[1], ..., a[n - 1]` を `dat` により初期化します.
43+
44+
計算量: $O(n)$
45+
46+
## メソッド
47+
48+
### set
49+
50+
```java
51+
public void set(int p, S x)
52+
```
53+
54+
`a[p]=x` とします．
55+
56+
計算量: $O(\log n)$
57+
58+
制約: `0 <= p < n`
59+
60+
### get
61+
62+
```java
63+
public S get(int p)
64+
```
65+
66+
`a[p]` を取得します．
67+
68+
計算量: $O(\log n)$
69+
70+
制約: `0 <= p < n`
71+
72+
### prod
73+
74+
```java
75+
public S prod(int l, int r)
76+
```
77+
78+
`op(a[l], ..., a[r - 1])` を、モノイドの性質を満たしていると仮定して計算します。`l = r` のときは単位元 `e` を返します。
79+
80+
計算量: $O(n)$
81+
82+
制約: `0 <= l <= r <= n`
83+
84+
### allProd
85+
86+
```java
87+
public S allProd()
88+
```
89+
90+
`op(a[0], ..., a[n - 1])` を、モノイドの性質を満たしていると仮定して計算します。`n = 0` のときは単位元 `e` を返します。
91+
92+
計算量: $O(1)$
93+
94+
### apply
95+
96+
```java
97+
// (1)
98+
public void apply(int p, F f)
99+
// (2)
100+
public void apply(int l, int r, F f)
101+
```
102+
103+
- (1): `a[p]` に作用素 `f` を作用させます
104+
- (2): `i∈[l, r)` に対して `a[i]` に作用素 `f` を作用させます
105+
106+
制約
107+
108+
- (1): `0 <= p < n`
109+
- (2): `0 <= l <= r <= n`
110+
111+
計算量
112+
113+
$O(\log n)$
114+
115+
### maxRight
116+
117+
```java
118+
public int maxRight(int l, java.util.function.Predicate<S> f)
119+
```
120+
121+
`S` を引数にとり `boolean` を返す関数を渡して使用します。
122+
以下の条件を両方満たす `r` を (いずれか一つ) 返します。
123+
124+
- `r = l` もしくは `f(op(a[l], a[l + 1], ..., a[r - 1])) = true`
125+
- `r = n` もしくは `f(op(a[l], a[l + 1], ..., a[r])) = false`
126+
127+
`f` が単調だとすれば、`f(op(a[l], a[l + 1], ..., a[r - 1])) = true` となる最大の `r`、と解釈することが可能です。
128+
129+
制約
130+
131+
- `f` を同じ引数で呼んだ時、返り値は等しい(=副作用はない)
132+
- __`f(e) = true`__
133+
- `0 <= l <= n`
134+
計算量
135+
136+
$O(\log n)$
137+
138+
### minLeft
139+
140+
```java
141+
public int minLeft(int r, java.util.function.Predicate<S> f)
142+
```
143+
144+
`S` を引数にとり `boolean` を返す関数オブジェクトを渡して使用します。
145+
以下の条件を両方満たす `l` を (いずれか一つ) 返します。
146+
147+
- `l = r` もしくは `f(op(a[l], a[l + 1], ..., a[r - 1])) = true`
148+
- `l = 0` もしくは `f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false`
149+
150+
fが単調だとすれば、`f(op(a[l], a[l + 1], ..., a[r - 1])) = true` となる最小の `l`、と解釈することが可能です。
151+
152+
制約
153+
154+
- `f` を同じ引数で呼んだ時、返り値は等しい(=副作用はない)
155+
- `f(e) = true`
156+
- `0 <= r <= n`
157+
158+
計算量
159+
160+
$O(\log n)$

0 commit comments

Comments
 (0)