dkh.datastructure.segtreenaive source code

1 module dkh.datastructure.segtreenaive;
2 
3 import dkh.datastructure.segtree;
4 
5 /*
6 This file contain naive codes of segtree, you don't need to import this file usually.
7 If you want to use segtree, import dkh.dasatructure.segtree.
8 */
9 
10 import std.conv : to;
11 import std.functional : binaryFun;
12 import std.traits : isInstanceOf;
13 
14 static struct NaiveSimple(T, alias opTT, T eT) {
15     import std.conv : to;
16     alias DataType = T;
17     alias LazyType = void;
18     alias BinSearch = binSearchNaiveSimple;
19     T[] d;
20     @property size_t length() const { return d.length; }
21     this(uint n) {
22         d = new T[n];
23     }
24     this(T[] first) {
25         d = first.dup;
26     }
27     const(T) sum(uint l, uint r) {
28         T sm = eT;
29         foreach (i; l..r) {
30             sm = opTT(sm, d[i]);
31         }
32         return sm;
33     }
34     const(T) single(int k) { return d[k]; }
35     void singleSet(int k, in T x) { d[k] = x; }
36 }
37 
38 static struct NaiveLazy(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL) {
39     import std.conv : to;
40     alias DataType = T;
41     alias LazyType = L;
42     alias BinSearch = binSearchNaiveLazy;
43     T[] d;
44     @property size_t length() const { return d.length; }
45     this(uint n) {
46         d = new T[n];
47     }
48     this(T[] first) {
49         d = first.dup;
50     }
51     const(T) sum(uint l, uint r) {
52         T sm = eT;
53         foreach (i; l..r) {
54             sm = opTT(sm, d[i]);
55         }
56         return sm;
57     }
58     void add(uint l, uint r, in L m) {
59         foreach (i; l..r) {
60             d[i] = opTL(d[i], m);
61         }
62     }
63     const(T) single(int k) { return d[k]; }
64     void singleSet(int k, in T x) { d[k] = x; }
65 }
66 
67 
68 int binSearchNaiveSimple(bool rev, alias pred, TR)(TR t, int a, int b) {
69     import std.traits : TemplateArgsOf;
70     alias args = TemplateArgsOf!TR;
71     alias opTT = args[1];
72     auto x = args[2];
73     with (t) {
74         static if (!rev) {
75             //left
76             if (pred(x)) return a-1;
77             foreach (i; a..b) {
78                 x = opTT(x, d[i]);
79                 if (pred(x)) return i;
80             }
81             return b;
82         } else {
83             if (pred(x)) return b;
84             foreach_reverse (i; a..b) {
85                 x = opTT(d[i], x);
86                 if (pred(x)) return i;
87             }
88             return a-1;
89         }
90     }
91 }
92 
93 int binSearchNaiveLazy(bool rev, alias pred, TR)(TR t, int a, int b) {
94     import std.traits : TemplateArgsOf;
95     alias args = TemplateArgsOf!TR;
96     alias opTT = args[2];
97     auto x = args[5];
98     with (t) {
99         static if (!rev) {
100             //left
101             if (pred(x)) return a-1;
102             foreach (i; a..b) {
103                 x = opTT(x, d[i]);
104                 if (pred(x)) return i;
105             }
106             return b;
107         } else {
108             if (pred(x)) return b;
109             foreach_reverse (i; a..b) {
110                 x = opTT(d[i], x);
111                 if (pred(x)) return i;
112             }
113             return a-1;
114         }
115     }
116 }
117 
118 unittest {
119     import std.traits : AliasSeq;
120     alias SimpleEngines = AliasSeq!(SimpleSegEngine);
121     alias LazyEngines = AliasSeq!(LazySegEngine);
122 
123     import std.random;
124     
125     void f(alias T)() {
126         auto nav = LazySeg!(uint, uint,
127             (a, b) => (a | b),
128             (a, b) => (a | b),
129             (a, b) => (a | b),
130             0U, 0U, NaiveLazy)(100);
131         auto seg = LazySeg!(uint, uint,
132             (a, b) => (a | b),
133             (a, b) => (a | b),
134             (a, b) => (a | b),
135             0U, 0U, T)(100);
136         foreach (i; 0..100) {
137             auto u = uniform!"[]"(0, 31);
138             seg[i] = u;
139             nav[i] = u;
140         }
141         foreach (i; 0..100) {
142             foreach (j; i..101) {
143                 foreach (x; 0..32) {
144                     assert(
145                         nav.binSearchLeft!((a) => a & x)(i, j) ==
146                         seg.binSearchLeft!((a) => a & x)(i, j));
147                     assert(seg.binSearchLeft!((a) => true)(i, j) == i-1);
148                     assert(
149                         nav.binSearchRight!((a) => a & x)(i, j) ==
150                         seg.binSearchRight!((a) => a & x)(i, j));
151                     assert(seg.binSearchRight!((a) => true)(i, j) == j);
152                 }
153             }
154         }
155     }
156     void g(alias T)() {
157         auto nav = SimpleSeg!(uint,
158             (a, b) => (a | b),
159             0U, NaiveSimple)(100);
160         auto seg = SimpleSeg!(uint,
161             (a, b) => (a | b),
162             0U, T)(100);
163         foreach (i; 0..100) {
164             auto u = uniform!"[]"(0, 31);
165             seg[i] = u;
166             nav[i] = u;
167         }
168         foreach (i; 0..100) {
169             foreach (j; i..101) {
170                 foreach (x; 0..32) {
171                     assert(
172                         nav.binSearchLeft!((a) => a & x)(i, j) ==
173                         seg.binSearchLeft!((a) => a & x)(i, j));
174                     assert(seg.binSearchLeft!((a) => true)(i, j) == i-1);
175                     assert(
176                         nav.binSearchRight!((a) => a & x)(i, j) ==
177                         seg.binSearchRight!((a) => a & x)(i, j));
178                     assert(seg.binSearchRight!((a) => true)(i, j) == j);
179                 }
180             }
181         }
182     }
183     foreach (E; LazyEngines) {
184         f!E();
185     }
186     foreach (E; SimpleEngines) {
187         g!E();
188     }
189 }
190 
191 unittest {
192     //some func test
193     import std.traits : AliasSeq;
194     alias SimpleEngines = AliasSeq!(SimpleSegEngine);
195     alias LazyEngines = AliasSeq!(LazySegEngine);
196     
197     void checkSimple(alias Seg)() {
198         import std.algorithm : max;
199         
200         alias S = SegTree!(Seg, int, (a, b) => a+b, 0);
201         S seg;
202         seg = S(10);
203         assert(seg.length == 10);
204     }
205     void check(alias Seg)() {
206         import std.algorithm : max;
207 
208         alias S = SegTree!(Seg, int, int,
209             (a, b) => max(a, b), (a, b) => a+b, (a, b) => a+b, 0, 0); 
210         S seg;
211         seg = S([2, 1, 4]);
212         
213         //[2, 1, 4]
214         seg[0] = 2; seg[1] = 1; seg[2] = 4;
215         assert(seg[0..3].sum == 4);
216 
217         //[2, 1, 5]
218         seg[2] = 5;
219         assert(seg[0..2].sum == 2);
220         assert(seg[0..3].sum == 5);
221 
222         //[12, 11, 5]
223         seg[0..2] += 10;
224         assert(seg[0..3].sum == 12);
225 
226         //n=10
227         auto seg2 = SegTree!(Seg, int, int,
228             (a, b) => max(a, b), (a, b) => a+b, (a, b) => a+b, 0, 0)(10);
229         assert(seg2.length == 10);
230     }
231 
232     foreach (E; SimpleEngines) {
233         checkSimple!E();
234     }
235     foreach (E; LazyEngines) {
236         check!E();
237     }
238 }
239 
240 unittest {
241     //stress test
242     import std.traits : AliasSeq;
243     alias SimpleEngines = AliasSeq!(SimpleSegEngine);
244     alias LazyEngines = AliasSeq!(LazySegEngine);
245 
246     import std.typecons, std.random, std.algorithm;
247     import dkh.modint, dkh.matrix, dkh.numeric.primitive;
248     static immutable uint MD = 10^^9 + 7;
249     alias Mint = ModInt!MD;
250     alias Mat = SMatrix!(Mint, 2, 2);
251 
252     static immutable Mat e = matrix!(2, 2, (i, j) => Mint(i == j ? 1 : 0))();
253 
254     Xorshift128 gen;
255 
256     Mat rndM() {
257         Mat m;
258         while (true) {
259             m = matrix!(2, 2, (i, j) => Mint(uniform(0, MD, gen)))();
260             if (m[0, 0] * m[1, 1] == m[0, 1] * m[1, 0]) continue;
261             break;
262         }
263         return m;
264     }
265 
266     Mat checkSimple(alias Seg)(int N, int M, uint seed) {
267         alias T = Tuple!(Mat, int);
268         gen = Xorshift128(seed);
269         Mat[] a = new Mat[N];
270         a.each!((ref x) => x = rndM());
271         alias Q = Tuple!(int, int, int, Mat);
272         Q[] que = new Q[M];
273         foreach (ref q; que) {
274             q[0] = uniform(0, 2, gen);
275             if (N == 0) q[0] = 0;
276             if (q[0] == 0) {
277                 q[1] = uniform(0, N+1, gen);
278                 q[2] = uniform(0, N+1, gen);
279                 if (q[1] > q[2]) swap(q[1], q[2]);
280             } else {
281                 q[1] = uniform(0, N, gen);
282             }
283             q[3] = rndM();
284         }
285         static auto opTT(Mat a, Mat b) {
286             return a*b;
287         }
288 
289         auto s = SegTree!(Seg, Mat, opTT, e)(a);
290         Mat res;
291         foreach (q; que) {
292             if (q[0] == 0) {
293                 //sum
294                 res += s[q[1]..q[2]].sum();
295             } else if (q[0] == 1) {
296                 //set
297                 s[q[1]] = q[3];
298             }
299         }
300         return res;
301     }    
302     Mat check(alias Seg)(int N, int M, uint seed) {
303         alias T = Tuple!(Mat, int);
304         gen = Xorshift128(seed);
305         T[] a = new T[N];
306         a.each!((ref x) => x = T(rndM(), 1));
307         alias Q = Tuple!(int, int, int, Mat);
308         Q[] que = new Q[M];
309         foreach (ref q; que) {
310             q[0] = uniform(0, 4, gen);
311             if (N == 0) q[0] %= 2;
312             if (q[0] < 2) {
313                 q[1] = uniform(0, N+1, gen);
314                 q[2] = uniform(0, N+1, gen);
315                 if (q[1] > q[2]) swap(q[1], q[2]);
316             } else {
317                 q[1] = uniform(0, N, gen);
318             }
319             q[3] = rndM();
320         }
321         static auto opTT(T a, T b) {
322             return T(a[0]*b[0], a[1]+b[1]);
323         }
324         static auto opTL(T a, Mat b) {
325             if (b == Mat()) return a;
326             return T(pow(b, a[1], e), a[1]);
327         }
328         static auto opLL(Mat a, Mat b) {
329             return b;
330         }
331 
332         auto s = SegTree!(Seg, T, Mat, opTT, opTL, opLL, T(e, 0), Mat())(a);
333         Mat res;
334         foreach (q; que) {
335             if (q[0] == 0) {
336                 //sum
337                 res += s[q[1]..q[2]].sum()[0];
338             } else if (q[0] == 1) {
339                 //set
340                 s[q[1]..q[2]] += q[3];
341             } else if (q[0] == 2) {
342                 //single sum
343                 T w = s[q[1]];
344                 res += w[0];
345             } else if (q[0] == 3) {
346                 //single set
347                 s[q[1]] = T(q[3], 1);
348             }
349         }
350         return res;
351     }
352 
353     import dkh.stopwatch;
354     StopWatch sw; sw.start;
355 
356     int n = 40;
357     Mat[] ansLazy = new Mat[n];
358     foreach (i; 0..n) {
359         ansLazy[i] = check!NaiveLazy(i, 500, 114514);
360     }
361     Mat[] ansSimple = new Mat[n];
362     foreach (i; 0..n) {
363         ansSimple[i] = checkSimple!NaiveSimple(i, 500, 114514);
364     }
365     
366     foreach (E; SimpleEngines) {
367         foreach (i; 0..n) {
368             assert(checkSimple!E(i, 500, 114514) == ansSimple[i]);
369         }
370     }
371     foreach (E; LazyEngines) {
372         foreach (i; 0..n) {
373             assert(check!E(i, 500, 114514) == ansLazy[i]);
374         }
375     }
376 
377     import std.stdio;
378     writeln("SegTree Stress: ", sw.peek.toMsecs);
379 }