仓库源文，站点原文

title: 「线段树的扩展之浅谈zkw线段树」一文的测试代码、数据、详细测试结果与生成器 tags:

算法竞赛
洛谷日报
测试 date: 2018-08-08 13:05:56 comments: false

测试代码

注意: 因为笔者脑抽并没有调用 fread

递归线段树

<details open> <summary>Show code</summary> {% icodeweb blog lang:cpp zkw-segment-tree-test1/seg-r.cpp %} </details>

zkw 线段树

<details open> <summary>Show code</summary> {% icodeweb blog lang:cpp zkw-segment-tree-test1/seg-zkw.cpp %} </details>

树状数组

<details open> <summary>Show code</summary> {% icodeweb blog lang:cpp zkw-segment-tree-test1/bit.cpp %} </details>

详细评测结果#1（以秒为单位）

test#1:
time#1 = 3.447280
time#2 = 3.696011
time#3 = 3.683904
time#4 = 3.648302
time#5 = 3.296298
time#6 = 7.708645
time#7 = 7.082259
time#8 = 7.126166
time#9 = 6.963065
time#10 = 7.756587
time#11 = 51.682691
time#12 = 48.633226
time#13 = 47.932671
time#14 = 105.835116
time#15 = 113.755264
time#16 = 158.988079
Ave:
3.554359
7.327344
49.416196
126.192820

test#2:
time#1 = 2.511897
time#2 = 1.695306
time#3 = 2.118245
time#4 = 2.079538
time#5 = 1.934902
time#6 = 4.719447
time#7 = 4.817881
time#8 = 4.623501
time#9 = 5.097146
time#10 = 5.355650
time#11 = 34.865590
time#12 = 34.907769
time#13 = 32.463151
time#14 = 74.738552
time#15 = 73.855234
time#16 = 74.000259
Ave:
2.067978
4.922725
34.078837
74.198015

test#3:
time#1 = 2.060278
time#2 = 1.992258
time#3 = 2.002796
time#4 = 1.820297
time#5 = 1.964742
time#6 = 4.490217
time#7 = 4.383801
time#8 = 4.159582
time#9 = 4.358566
time#10 = 4.404194
time#11 = 26.816804
time#12 = 26.666548
time#13 = 26.862968
time#14 = 57.438784
time#15 = 57.584326
time#16 = 57.433181
Ave:
1.968074
4.359272
26.782107
57.485430

详细评测结果#2（以秒为单位）

test#1:
time#1 = 3.723513
time#2 = 4.895209
time#3 = 4.096053
time#4 = 3.921210
time#5 = 3.291190
time#6 = 6.779961
time#7 = 7.278650
time#8 = 7.048792
time#9 = 6.539919
time#10 = 7.330734
time#11 = 45.730535
time#12 = 45.291213
time#13 = 45.184196
time#14 = 99.981685
time#15 = 99.947381
time#16 = 99.487397
Ave:
3.985435
6.995611
45.401981
99.805488

test#2:
time#1 = 1.830346
time#2 = 2.099576
time#3 = 2.085104
time#4 = 2.171504
time#5 = 2.239576
time#6 = 4.618806
time#7 = 3.836848
time#8 = 4.119962
time#9 = 4.149363
time#10 = 4.619962
time#11 = 29.606656
time#12 = 29.431768
time#13 = 29.710447
time#14 = 67.893993
time#15 = 66.520776
time#16 = 68.217186
Ave:
2.085221
4.268988
29.582957
67.543985

test#3:
time#1 = 1.943302
time#2 = 2.128660
time#3 = 2.122796
time#4 = 1.828443
time#5 = 1.882570
time#6 = 3.893438
time#7 = 4.130842
time#8 = 3.821628
time#9 = 3.872965
time#10 = 4.239745
time#11 = 25.007103
time#12 = 25.088401
time#13 = 25.442503
time#14 = 54.489850
time#15 = 54.187768
time#16 = 54.235232
Ave:
1.981154
3.991724
25.179336
54.304283

{% post_link zkw-segment-tree 回到原文 %}