22:
1934:
This contrasts with other range query problems, such as the range minimum query which have solutions offering constant time query time and linear space. This is due to the hardness of the mode problem, since even if we know the mode of
7790:
6301:
1929:
7852:
7714:
6707:
4154:
5435:
is either an element of the prefix, span or suffix. A linear scan is performed over each element in the prefix and in the suffix to check if its frequency is greater than the current candidate
498:
8176:
6303:
space for a constant time query. We can observe that, if a constant query time is desired, this is a better solution than the one proposed by Chan et al., as the latter gives a space of
5002:
4949:
3583:
3204:
1591:
1495:
8079:
1806:
1669:
7441:
3254:
1765:
6515:
3860:
6555:
3900:
3318:
1719:
265:
3772:
3408:
1628:
1403:
7233:
6008:
2492:
7373:
5688:
5212:
2859:
1325:
1198:
40:
2797:
6119:
7910:
7514:
7297:
7265:
6879:
6827:
6795:
6217:
4890:
4323:
227:
2730:
7593:
6601:
4393:
2271:
2179:
1158:
938:
906:
832:
610:
6743:
6337:
4288:
5398:
5365:
4252:
4034:
3608:
3442:
3358:
2957:
2640:
2419:
2351:
806:
303:
4527:
S ← c Sprime ← fc noBlock ← noBlock + 1 block_end ← min{block_end + t, n - 1}
2767:
7324:
6044:
5891:
5823:
5582:
5500:
5311:
4629:
3927:
3498:
2298:
2206:
1072:
965:
434:
407:
6079:
2826:
1525:
1361:
1291:
6363:
3116:
7194:
7130:
7087:
708:
566:
380:
177:
8196:
8119:
8099:
8029:
7970:
7950:
7930:
7613:
7554:
7534:
7461:
7107:
7064:
7044:
7009:
6974:
6954:
6934:
6899:
6847:
6636:
6575:
6450:
6430:
6406:
6165:
6145:
5955:
5920:
5858:
5796:
5761:
5729:
5613:
5555:
5520:
5473:
5453:
5433:
5284:
5235:
5172:
5088:
5022:
4837:
4817:
4797:
4777:
4757:
4722:
4693:
4658:
4597:
4577:
4362:
4343:
4227:
4083:
4009:
3989:
3795:
3695:
3675:
3640:
3518:
3462:
3136:
3090:
3070:
3041:
3012:
2992:
2937:
2902:
2680:
2660:
2587:
2567:
2547:
2527:
2460:
2386:
2318:
2120:
2079:
2044:
2009:
1968:
1858:
1838:
1424:
1238:
1218:
1132:
1112:
1092:
1045:
1025:
1005:
985:
872:
852:
780:
756:
736:
7171:
6167:. A further analysis of the linear scans done for frequency computations shows that it is also bounded by the block size. Thus, the query time is
612:
because it occurs three times, while all other values occur fewer times. In this problem, the queries ask for the mode of subarrays of the form
7719:
6230:
1863:
58:
75:, the range mode query problem asks to build a data structure on some input data to efficiently answer queries asking for the
7795:
7622:
6641:
4088:
8297:
Greve, M; Jørgensen, A.; Larsen, K.; Truelsen, J. (2010). "Cell probe lower bounds and approximations for range mode".
439:
4954:
4895:
3523:
3144:
1537:
1435:
1771:
1634:
7378:
3209:
1725:
6455:
3991:. The mode and the frequency of each block or set of consecutive blocks will be pre-computed in two tables
3800:
8226:
Chan, Timothy M.; Durocher, Stephane; Larsen, Kasper Green; Morrison, Jason; Wilkinson, Bryan T. (2013).
6520:
3865:
3259:
1679:
232:
8124:
3700:
3363:
1597:
1367:
8279:
7199:
2465:
7329:
5622:
5177:
2831:
1297:
1163:
8034:
5592:
The procedure is similar for both prefix and suffix, so it suffice to run this procedure for both:
2772:
8178:
that contains the positions of the mode for these blocks and use the position to find the mode in
7912:, check if it is completely contained inside a block, in which case the answer is stored in table
6084:
8269:
7865:
7469:
6750:
6170:
4845:
4293:
182:
5960:
5174:(the set of indices after the span). The prefix, suffix or span can be empty, the latter is if
2693:
8258:
7559:
6580:
2211:
2125:
1137:
911:
885:
811:
571:
6712:
6306:
4257:
76:
5370:
2942:
2592:
2391:
2323:
785:
270:
7270:
7238:
6852:
6800:
2735:
7302:
6013:
5869:
5801:
5560:
5478:
5289:
4602:
3905:
3467:
2276:
2184:
1050:
943:
412:
385:
8318:
6049:
4367:
2802:
1501:
1337:
1267:
6342:
3095:
8283:
7176:
7112:
7069:
5316:
5004:. These denote the indices of the first and last block that are completely contained in
4232:
4014:
3588:
3413:
3323:
615:
503:
308:
90:
8181:
8104:
8084:
7975:
7955:
7935:
7915:
7598:
7539:
7519:
7446:
7092:
7049:
7014:
6979:
6959:
6939:
6904:
6884:
6832:
6606:
6560:
6435:
6415:
6376:
6150:
6130:
5925:
5896:
5828:
5766:
5737:
5693:
5598:
5525:
5505:
5458:
5438:
5403:
5240:
5220:
5093:
5027:
5007:
4822:
4802:
4782:
4762:
4727:
4698:
4663:
4634:
4582:
4562:
4347:
4328:
4159:
4039:
3994:
3932:
3780:
3680:
3645:
3616:
3503:
3447:
3121:
3075:
3046:
3017:
2997:
2962:
2907:
2872:
2665:
2645:
2572:
2552:
2532:
2497:
2424:
2356:
2303:
2084:
2049:
2014:
1973:
1938:
1843:
1823:
1409:
1223:
1203:
1117:
1097:
1077:
1030:
1010:
990:
970:
857:
837:
765:
741:
721:
72:
7135:
8312:
6127:
This linear scan (excluding the frequency computations) is bounded by the block size
7932:. If the query spans exactly one or more blocks, then the answer is found in table
7443:. To access those tables, a pointer is added in addition to the mode in the table
8227:
5825:(this can be done in constant time since it is the equivalent of checking it for
4892:, the query is split in three parts: the prefix, the span and the suffix. Let
8254:
6976:. By Theorem 1, the mode can be either an element of the prefix (indices of
759:
7785:{\displaystyle O\left({\frac {n^{2}\log {\log {n}}}{\log {n}}}\right)}
6296:{\displaystyle O\left({\frac {n^{2}\log {\log {n}}}{\log {n}}}\right)}
4254:
stores the corresponding frequency. These two tables can be stored in
3613:
It is now possible to answer queries of the form "is the frequency of
7556:
are in the same block, all such solutions are precomputed. There are
5731:
and its frequency has already been counted. Pass to the next element.
7089:, thus the position of the mode isstored as an integer ranging from
7011:
before the start of the span), an element of the suffix (indices of
8274:
7066:. The size of the prefix plus the size of the suffix is bounded by
5024:. The range of these blocks is called the span. The prefix is then
1924:{\displaystyle \Omega \left({\frac {\log n}{\log(Sw/n)}}\right)}
15:
8228:"Linear-Space Data Structures for Range Mode Query in Arrays"
6147:, since neither the prefix or the suffix can be greater than
6901:. Let the span be the set of blocks completely contained in
5615:
be the index of the current element. There are three cases:
7196:
indicates that the mode is the mode of the span. There are
7375:
such tables, so the total space required for this step is
6223:
Subquadratic space data structure with constant query time
4516:c ← B fc ← fc + 1
2939:
be an array that contains the distinct values of A, where
8259:"Range Mode and Range Median Queries on Lists and Trees"
8081:
are the indices of the blocks that contain respectively
5090:(the set of indices before the span), and the suffix is
6408:
be an array. The preprocessing is done in three steps:
2686:
Linear space data structure with square root query time
36:
7595:
of them, they are stored in a three dimensional table
5502:
are updated to the new value. At the end of the scan,
4512:
atLeastQInstances(firstOccurence], block_end, fc + 1)
8184:
8127:
8107:
8087:
8037:
7978:
7958:
7938:
7918:
7868:
7798:
7722:
7625:
7601:
7562:
7542:
7522:
7472:
7449:
7381:
7332:
7305:
7273:
7241:
7202:
7179:
7138:
7115:
7095:
7072:
7052:
7017:
6982:
6962:
6942:
6907:
6887:
6855:
6835:
6803:
6753:
6715:
6644:
6609:
6583:
6563:
6523:
6458:
6438:
6418:
6379:
6345:
6309:
6233:
6173:
6153:
6133:
6087:
6052:
6016:
5963:
5928:
5899:
5872:
5831:
5804:
5769:
5740:
5696:
5625:
5601:
5563:
5528:
5508:
5481:
5461:
5441:
5406:
5373:
5319:
5292:
5243:
5223:
5180:
5096:
5030:
5010:
4957:
4898:
4848:
4825:
4805:
4785:
4765:
4730:
4701:
4666:
4637:
4605:
4585:
4565:
4370:
4350:
4331:
4296:
4260:
4235:
4162:
4091:
4042:
4017:
3997:
3935:
3908:
3868:
3803:
3783:
3703:
3683:
3648:
3619:
3591:
3526:
3506:
3470:
3450:
3416:
3366:
3326:
3262:
3212:
3147:
3124:
3098:
3078:
3049:
3020:
3000:
2965:
2945:
2910:
2875:
2834:
2805:
2775:
2738:
2696:
2668:
2648:
2595:
2575:
2555:
2535:
2500:
2468:
2427:
2394:
2359:
2326:
2306:
2279:
2214:
2187:
2128:
2087:
2052:
2017:
1976:
1941:
1866:
1846:
1826:
1774:
1728:
1682:
1637:
1600:
1540:
1504:
1438:
1412:
1370:
1340:
1300:
1270:
1226:
1206:
1166:
1140:
1120:
1100:
1080:
1053:
1033:
1013:
993:
973:
946:
914:
888:
860:
840:
814:
788:
768:
744:
724:
618:
574:
506:
442:
415:
388:
311:
273:
235:
185:
93:
7847:{\displaystyle t={\sqrt {\log {n}/\log {\log {n}}}}}
7709:{\displaystyle O(s^{2}+t^{2}(2t+1)^{t^{2}}+st^{2})}
6702:{\displaystyle b_{i}\cup b_{i+1}\cup ...\cup b_{j}}
4149:{\displaystyle b_{i}\cup b_{i+1}\cup ...\cup b_{j}}
31:
may be too technical for most readers to understand
8190:
8170:
8113:
8093:
8073:
8023:
7964:
7944:
7924:
7904:
7846:
7784:
7708:
7607:
7587:
7548:
7528:
7508:
7455:
7435:
7367:
7318:
7291:
7259:
7227:
7188:
7165:
7124:
7101:
7081:
7058:
7038:
7003:
6968:
6948:
6928:
6893:
6873:
6841:
6821:
6789:
6737:
6701:
6630:
6595:
6569:
6549:
6509:
6444:
6424:
6400:
6357:
6331:
6295:
6211:
6159:
6139:
6113:
6073:
6038:
6002:
5949:
5914:
5885:
5852:
5817:
5790:
5755:
5723:
5682:
5607:
5576:
5549:
5514:
5494:
5467:
5447:
5427:
5392:
5359:
5305:
5278:
5229:
5206:
5166:
5082:
5016:
4996:
4943:
4884:
4831:
4811:
4791:
4771:
4751:
4716:
4687:
4652:
4623:
4591:
4571:
4387:
4356:
4337:
4317:
4282:
4246:
4221:
4148:
4077:
4028:
4003:
3983:
3921:
3894:
3854:
3789:
3766:
3689:
3669:
3634:
3602:
3577:
3512:
3492:
3456:
3436:
3402:
3352:
3312:
3248:
3198:
3130:
3110:
3084:
3064:
3035:
3006:
2986:
2951:
2931:
2896:
2853:
2820:
2791:
2761:
2724:
2674:
2654:
2634:
2581:
2561:
2541:
2521:
2486:
2454:
2413:
2380:
2345:
2312:
2292:
2265:
2200:
2173:
2114:
2073:
2038:
2011:, there is no simple way of computing the mode of
2003:
1962:
1923:
1852:
1832:
1800:
1759:
1713:
1663:
1622:
1585:
1519:
1489:
1418:
1397:
1355:
1319:
1285:
1232:
1212:
1192:
1152:
1126:
1106:
1086:
1066:
1039:
1019:
999:
979:
959:
932:
900:
866:
846:
826:
800:
774:
750:
730:
702:
604:
560:
492:
428:
401:
374:
297:
259:
221:
171:
7219:
7206:
5313:be the frequency of the mode, which is stored in
7299:, so these values are stored in a table of size
7619:The total space used by this data structure is
493:{\displaystyle s_{j}\;\forall j\in \{1,...,k\}}
7173:indicates a position in the prefix/suffix and
4559:We will define the query algorithm over array
2959:is the number of distinct elements. We define
7952:. Otherwise, use the pointer stored in table
436:is greater than or equal to the frequency of
8:
6544:
6530:
5866:If it is, then compute the actual frequency
5863:If it is not, then pass to the next element.
5152:
5112:
5074:
5052:
4985:
4971:
4938:
4912:
4490:← min{(i + 1) × t - 1, n - 1}
3889:
3875:
3397:
3373:
3307:
3276:
3243:
3219:
487:
463:
4997:{\displaystyle b_{j}=\lfloor j/t\rfloor -1}
4944:{\displaystyle b_{i}=\lceil (i-1)/t\rceil }
4579:. This can be translated to an answer over
3578:{\displaystyle Q_{1},Q_{2},...,Q_{\Delta }}
3199:{\displaystyle Q_{1},Q_{2},...,Q_{\Delta }}
8221:
8219:
8217:
8215:
8213:
8211:
3288:
3282:
1586:{\displaystyle O(n^{2-2\epsilon }/\log n)}
1490:{\displaystyle O(n^{2}\log \log n/\log n)}
453:
8273:
8183:
8155:
8137:
8132:
8126:
8106:
8086:
8060:
8042:
8036:
8007:
7989:
7977:
7957:
7937:
7917:
7867:
7836:
7829:
7818:
7813:
7805:
7797:
7770:
7756:
7749:
7737:
7730:
7721:
7697:
7679:
7674:
7649:
7636:
7624:
7600:
7576:
7561:
7541:
7521:
7471:
7448:
7422:
7417:
7392:
7380:
7357:
7352:
7331:
7310:
7304:
7278:
7272:
7246:
7240:
7218:
7205:
7203:
7201:
7178:
7137:
7114:
7094:
7071:
7051:
7016:
6981:
6961:
6941:
6906:
6886:
6860:
6854:
6834:
6808:
6802:
6752:
6726:
6714:
6693:
6662:
6649:
6643:
6608:
6582:
6562:
6536:
6522:
6501:
6476:
6463:
6457:
6437:
6417:
6378:
6344:
6320:
6308:
6281:
6267:
6260:
6248:
6241:
6232:
6198:
6172:
6152:
6132:
6105:
6092:
6086:
6051:
6021:
6015:
5988:
5962:
5927:
5898:
5877:
5871:
5830:
5809:
5803:
5768:
5739:
5695:
5630:
5624:
5600:
5568:
5562:
5527:
5507:
5486:
5480:
5460:
5440:
5405:
5400:. Recall that, by Theorem 1, the mode of
5378:
5372:
5348:
5335:
5318:
5297:
5291:
5267:
5254:
5242:
5222:
5198:
5185:
5179:
5122:
5095:
5059:
5029:
5009:
4977:
4962:
4956:
4930:
4903:
4897:
4847:
4824:
4804:
4784:
4764:
4729:
4700:
4665:
4636:
4604:
4584:
4564:
4369:
4349:
4330:
4295:
4271:
4259:
4234:
4198:
4173:
4161:
4140:
4109:
4096:
4090:
4066:
4053:
4041:
4016:
3996:
3934:
3913:
3907:
3881:
3867:
3846:
3821:
3808:
3802:
3782:
3708:
3702:
3682:
3647:
3618:
3590:
3569:
3544:
3531:
3525:
3505:
3475:
3469:
3449:
3415:
3365:
3325:
3283:
3267:
3261:
3211:
3190:
3165:
3152:
3146:
3123:
3097:
3077:
3048:
3019:
2999:
2964:
2944:
2909:
2874:
2841:
2833:
2804:
2782:
2774:
2748:
2737:
2713:
2695:
2667:
2647:
2594:
2574:
2554:
2534:
2499:
2467:
2426:
2399:
2393:
2358:
2331:
2325:
2305:
2284:
2278:
2213:
2192:
2186:
2127:
2086:
2051:
2016:
1975:
1940:
1903:
1874:
1865:
1845:
1825:
1790:
1773:
1739:
1727:
1693:
1681:
1653:
1636:
1611:
1599:
1566:
1551:
1539:
1503:
1470:
1449:
1437:
1411:
1382:
1377:
1369:
1339:
1307:
1299:
1269:
1225:
1205:
1184:
1171:
1165:
1139:
1119:
1099:
1079:
1058:
1052:
1032:
1012:
992:
972:
951:
945:
913:
887:
859:
839:
813:
787:
767:
743:
723:
691:
660:
647:
617:
573:
505:
447:
441:
420:
414:
393:
387:
363:
338:
325:
310:
272:
234:
184:
160:
135:
122:
92:
59:Learn how and when to remove this message
43:, without removing the technical details.
4439:← Table(0:n - 1, 0:n - 1) let
4435:← Table(0:n - 1, 0:n - 1) let
4395:each time with the following algorithm:
3697:" in constant time, by checking whether
1247:
179:, we wish to answer queries of the form
79:of any consecutive subset of the input.
8248:
8246:
8244:
8207:
1801:{\displaystyle 0\leq \epsilon \leq 1/2}
1664:{\displaystyle 0\leq \epsilon \leq 1/2}
7436:{\displaystyle O(t^{2}(2t+1)^{t^{2}})}
4505:firstOccurence] ← j
3249:{\displaystyle a\in \{1,...,\Delta \}}
3206:are also created, such that, for each
1760:{\displaystyle O(n^{\epsilon }\log n)}
8198:. This can be done in constant time.
6510:{\displaystyle b_{1},b_{2},...,b_{s}}
5734:Otherwise, check if the frequency of
3855:{\displaystyle b_{1},b_{2},...,b_{s}}
41:make it understandable to non-experts
7:
5957:by a linear scan (starting at index
8299:Automata, Languages and Programming
6956:of the block can be retrieved from
6709:. The total space for this step is
6550:{\displaystyle t=\lceil n/s\rceil }
4545:firstOccurence ← -1
3895:{\displaystyle t=\lceil n/s\rceil }
3313:{\displaystyle Q_{a}=\{b\;|\;B=a\}}
3118:can be created by a linear scan of
2994:to be an array such that, for each
2122:could be the mode. For example, if
1931:time to answer a range mode query.
1714:{\displaystyle O(n^{2-2\epsilon })}
260:{\displaystyle 1\leq i\leq j\leq n}
7235:possible queries involving blocks
7210:
6517:, where the size of each block is
3570:
3240:
3191:
2946:
2923:
1867:
454:
14:
8171:{\displaystyle U_{b_{i'},b_{j'}}}
2861:bounds for space and query time.
2529:is greater than the frequency of
3767:{\displaystyle Q_{B}+q-1]\leq j}
3403:{\displaystyle b\in \{1,...,n\}}
3043:contains the rank (position) of
2690:This method by Chan et al. uses
1623:{\displaystyle O(n^{\epsilon })}
1398:{\displaystyle O({\sqrt {n/w}})}
1027:. Thus, there exists an element
20:
7228:{\displaystyle {\binom {t}{2}}}
7046:after the end of the span), or
4799:in constant time by looking in
4759:. We can convert an answer for
4455:firstOccurence ← -1
4443:← Array(0:Delta - 1)
4290:space, and can be populated in
4156:, or equivalently, the mode of
2487:{\displaystyle a\not =c\not =b}
8257:; Smid, Michiel H. M. (2003).
8018:
7982:
7899:
7881:
7703:
7671:
7655:
7629:
7582:
7566:
7503:
7485:
7430:
7414:
7398:
7385:
7368:{\displaystyle (2t+1)^{t^{2}}}
7349:
7333:
7160:
7139:
7033:
7021:
6998:
6986:
6923:
6911:
6784:
6766:
6732:
6719:
6625:
6613:
6395:
6383:
6326:
6313:
6206:
6192:
6183:
6177:
6068:
6062:
6031:
6025:
5978:
5972:
5944:
5932:
5909:
5903:
5847:
5835:
5785:
5773:
5750:
5744:
5718:
5700:
5683:{\displaystyle Q_{B}-1]\geq i}
5671:
5662:
5656:
5645:
5640:
5634:
5544:
5532:
5422:
5410:
5354:
5328:
5273:
5247:
5207:{\displaystyle b_{j}<b_{i}}
5161:
5134:
5115:
5100:
5077:
5034:
4927:
4915:
4879:
4861:
4746:
4734:
4711:
4705:
4682:
4670:
4647:
4641:
4312:
4300:
4277:
4264:
4216:
4210:
4191:
4166:
4072:
4046:
3978:
3972:
3960:
3939:
3755:
3740:
3734:
3723:
3718:
3712:
3664:
3652:
3629:
3623:
3485:
3479:
3431:
3425:
3347:
3335:
3298:
3292:
3284:
3059:
3053:
3030:
3024:
2981:
2969:
2926:
2914:
2891:
2879:
2854:{\displaystyle O({\sqrt {n}})}
2848:
2838:
2815:
2809:
2756:
2742:
2719:
2700:
2629:
2626:
2614:
2608:
2516:
2504:
2449:
2431:
2375:
2363:
2254:
2251:
2233:
2227:
2162:
2159:
2147:
2141:
2109:
2091:
2068:
2056:
2033:
2021:
1998:
1980:
1957:
1945:
1911:
1894:
1754:
1732:
1708:
1686:
1617:
1604:
1580:
1544:
1514:
1508:
1484:
1442:
1392:
1374:
1350:
1344:
1320:{\displaystyle O({\sqrt {n}})}
1314:
1304:
1280:
1274:
1193:{\displaystyle f_{b}>f_{c}}
697:
640:
634:
622:
593:
587:
555:
513:
369:
318:
292:
286:
216:
198:
166:
115:
109:
97:
1:
8074:{\displaystyle b_{i'},b_{j'}}
2792:{\displaystyle s={\sqrt {n}}}
6114:{\displaystyle f_{c}:=f_{x}}
5367:. If the span is empty, let
4839:at the corresponding index.
2300:, there could be an element
8235:Theory of Computing Systems
7905:{\displaystyle mode(A,i,j)}
7509:{\displaystyle mode(A,i,j)}
6881:be the block that contains
6829:be the block that contains
6790:{\displaystyle mode(A,i,j)}
6339:for constant query time if
6212:{\displaystyle O(t)=O(n/s)}
4885:{\displaystyle mode(B,i,j)}
4318:{\displaystyle O(s\cdot n)}
409:such that the frequency of
222:{\displaystyle mode(A,i:j)}
8335:
6003:{\displaystyle B'+f_{c}-1}
4470:← i × t let
4364:times, computing a row of
3777:The array is split B into
3520:suffices to create arrays
3500:. Again, a linear scan of
3320:. We then create an array
2725:{\displaystyle O(n+s^{2})}
2273:and its frequency is also
1240:which is a contradiction.
7588:{\displaystyle O(st^{2})}
7326:. Furthermore, there are
6596:{\displaystyle s\times s}
5690:, then it was present in
2266:{\displaystyle mode(A)=b}
2174:{\displaystyle mode(A)=a}
1820:Any data structure using
1153:{\displaystyle c\notin A}
933:{\displaystyle C=A\cup B}
901:{\displaystyle c\notin A}
827:{\displaystyle c\notin A}
605:{\displaystyle mode(S)=2}
7463:for each pair of blocks.
6738:{\displaystyle O(s^{2})}
6332:{\displaystyle O(n^{2})}
6010:) or a binary search in
4283:{\displaystyle O(s^{2})}
5393:{\displaystyle f_{c}=0}
5217:For the span, the mode
2952:{\displaystyle \Delta }
2769:query time. By setting
2635:{\displaystyle mode(A)}
2589:a better candidate for
2494:, but its frequency in
2414:{\displaystyle f_{a}-1}
2346:{\displaystyle f_{a}-1}
801:{\displaystyle A\cup B}
298:{\displaystyle mode(S)}
8192:
8172:
8115:
8095:
8075:
8025:
7966:
7946:
7926:
7906:
7848:
7786:
7710:
7609:
7589:
7550:
7530:
7510:
7457:
7437:
7369:
7320:
7293:
7292:{\displaystyle b_{j'}}
7261:
7260:{\displaystyle b_{i'}}
7229:
7190:
7167:
7126:
7103:
7083:
7060:
7040:
7005:
6970:
6950:
6930:
6895:
6875:
6874:{\displaystyle b_{j'}}
6843:
6823:
6822:{\displaystyle b_{i'}}
6791:
6739:
6703:
6632:
6597:
6571:
6551:
6511:
6446:
6426:
6402:
6359:
6333:
6297:
6213:
6161:
6141:
6115:
6075:
6040:
6004:
5951:
5916:
5887:
5854:
5819:
5792:
5757:
5725:
5684:
5609:
5578:
5551:
5516:
5496:
5469:
5449:
5429:
5394:
5361:
5307:
5280:
5231:
5208:
5168:
5084:
5018:
4998:
4945:
4886:
4833:
4813:
4793:
4773:
4753:
4718:
4689:
4654:
4625:
4593:
4573:
4486:← j let
4482:← i let
4478:← 0 let
4474:← 0 let
4389:
4358:
4339:
4319:
4284:
4248:
4223:
4150:
4079:
4030:
4005:
3985:
3923:
3896:
3856:
3791:
3768:
3691:
3671:
3636:
3604:
3579:
3514:
3494:
3458:
3438:
3404:
3354:
3314:
3250:
3200:
3132:
3112:
3086:
3066:
3037:
3008:
2988:
2953:
2933:
2898:
2855:
2822:
2793:
2763:
2762:{\displaystyle O(n/s)}
2726:
2676:
2656:
2636:
2583:
2563:
2543:
2523:
2488:
2456:
2415:
2382:
2347:
2314:
2294:
2267:
2202:
2175:
2116:
2075:
2040:
2005:
1964:
1925:
1854:
1834:
1802:
1761:
1715:
1665:
1624:
1587:
1521:
1491:
1420:
1399:
1357:
1321:
1287:
1234:
1220:should be the mode of
1214:
1194:
1154:
1128:
1108:
1088:
1068:
1041:
1021:
1001:
981:
961:
934:
902:
868:
848:
828:
802:
776:
752:
732:
704:
606:
562:
494:
430:
403:
376:
299:
261:
223:
173:
8193:
8173:
8116:
8096:
8076:
8026:
7967:
7947:
7927:
7907:
7849:
7787:
7711:
7610:
7590:
7551:
7531:
7511:
7458:
7438:
7370:
7321:
7319:{\displaystyle t^{2}}
7294:
7262:
7230:
7191:
7168:
7127:
7104:
7084:
7061:
7041:
7006:
6971:
6951:
6931:
6896:
6876:
6844:
6824:
6792:
6740:
6704:
6633:
6598:
6572:
6552:
6512:
6447:
6427:
6403:
6360:
6334:
6298:
6227:This method by uses
6214:
6162:
6142:
6116:
6076:
6041:
6039:{\displaystyle Q_{B}}
6005:
5952:
5917:
5888:
5886:{\displaystyle f_{x}}
5855:
5820:
5818:{\displaystyle f_{c}}
5793:
5758:
5726:
5685:
5610:
5579:
5577:{\displaystyle f_{c}}
5552:
5522:contains the mode of
5517:
5497:
5495:{\displaystyle f_{c}}
5470:
5450:
5430:
5395:
5362:
5308:
5306:{\displaystyle f_{c}}
5281:
5237:is already stored in
5232:
5209:
5169:
5085:
5019:
4999:
4946:
4887:
4834:
4814:
4794:
4774:
4754:
4719:
4690:
4655:
4626:
4624:{\displaystyle a,i,j}
4594:
4574:
4501:firstOccurence] = -1
4416:= , Integer
4390:
4359:
4340:
4320:
4285:
4249:
4224:
4151:
4080:
4031:
4006:
3986:
3924:
3922:{\displaystyle b_{i}}
3897:
3857:
3792:
3769:
3692:
3672:
3637:
3605:
3580:
3515:
3495:
3493:{\displaystyle Q_{B}}
3459:
3444:contains the rank of
3439:
3405:
3360:, such that, for all
3355:
3315:
3251:
3201:
3133:
3113:
3087:
3067:
3038:
3009:
2989:
2954:
2934:
2899:
2856:
2823:
2794:
2764:
2727:
2677:
2657:
2637:
2584:
2564:
2544:
2524:
2489:
2457:
2416:
2383:
2348:
2315:
2295:
2293:{\displaystyle f_{a}}
2268:
2203:
2201:{\displaystyle f_{a}}
2181:and its frequency is
2176:
2117:
2076:
2041:
2006:
1965:
1926:
1855:
1835:
1803:
1762:
1716:
1666:
1625:
1588:
1522:
1492:
1421:
1400:
1358:
1322:
1288:
1235:
1215:
1195:
1155:
1129:
1109:
1089:
1069:
1067:{\displaystyle f_{b}}
1042:
1022:
1002:
982:
962:
960:{\displaystyle f_{c}}
935:
903:
869:
849:
829:
803:
777:
753:
733:
705:
607:
563:
495:
431:
429:{\displaystyle s_{i}}
404:
402:{\displaystyle s_{i}}
377:
300:
262:
224:
174:
8182:
8125:
8121:, to find the table
8105:
8085:
8035:
7976:
7956:
7936:
7916:
7866:
7796:
7720:
7623:
7599:
7560:
7540:
7520:
7470:
7447:
7379:
7330:
7303:
7271:
7239:
7200:
7177:
7136:
7113:
7093:
7070:
7050:
7015:
6980:
6960:
6940:
6905:
6885:
6853:
6833:
6801:
6751:
6713:
6642:
6607:
6581:
6561:
6521:
6456:
6436:
6416:
6377:
6343:
6307:
6231:
6171:
6151:
6131:
6085:
6074:{\displaystyle c:=B}
6050:
6014:
5961:
5926:
5897:
5870:
5829:
5802:
5767:
5738:
5694:
5623:
5599:
5561:
5526:
5506:
5479:
5459:
5439:
5404:
5371:
5317:
5290:
5241:
5221:
5178:
5094:
5028:
5008:
4955:
4896:
4846:
4823:
4803:
4783:
4763:
4728:
4699:
4664:
4635:
4603:
4583:
4563:
4541:{0, ..., Delta - 1}
4451:{0, ..., Delta - 1}
4388:{\displaystyle S,S'}
4368:
4348:
4329:
4294:
4258:
4233:
4160:
4089:
4040:
4015:
3995:
3933:
3906:
3866:
3801:
3781:
3701:
3681:
3646:
3617:
3589:
3524:
3504:
3468:
3448:
3414:
3364:
3324:
3260:
3210:
3145:
3122:
3096:
3076:
3047:
3018:
2998:
2963:
2943:
2908:
2873:
2832:
2821:{\displaystyle O(n)}
2803:
2773:
2736:
2694:
2666:
2646:
2593:
2573:
2553:
2533:
2498:
2466:
2425:
2392:
2357:
2324:
2304:
2277:
2212:
2185:
2126:
2085:
2050:
2015:
1974:
1939:
1864:
1844:
1824:
1772:
1726:
1680:
1635:
1598:
1538:
1520:{\displaystyle O(1)}
1502:
1436:
1410:
1368:
1356:{\displaystyle O(n)}
1338:
1298:
1286:{\displaystyle O(n)}
1268:
1224:
1204:
1164:
1138:
1118:
1098:
1078:
1074:that is the mode of
1051:
1031:
1011:
991:
971:
967:be its frequency in
944:
912:
886:
858:
838:
812:
786:
766:
742:
722:
616:
572:
504:
440:
413:
386:
309:
271:
233:
183:
91:
8284:2003cs........7034K
7716:, which reduces to
6358:{\displaystyle s=n}
4412:= , Array
3111:{\displaystyle B,D}
8188:
8168:
8111:
8091:
8071:
8021:
7962:
7942:
7922:
7902:
7844:
7782:
7706:
7605:
7585:
7546:
7526:
7506:
7466:To handle queries
7453:
7433:
7365:
7316:
7289:
7257:
7225:
7189:{\displaystyle 2t}
7186:
7163:
7125:{\displaystyle 2t}
7122:
7099:
7082:{\displaystyle 2t}
7079:
7056:
7036:
7001:
6966:
6946:
6926:
6891:
6871:
6839:
6819:
6787:
6735:
6699:
6628:
6593:
6567:
6547:
6507:
6442:
6422:
6398:
6355:
6329:
6293:
6209:
6157:
6137:
6111:
6071:
6036:
6000:
5947:
5912:
5883:
5850:
5815:
5788:
5753:
5721:
5680:
5605:
5588:Scanning procedure
5574:
5547:
5512:
5492:
5465:
5445:
5425:
5390:
5360:{\displaystyle S'}
5357:
5303:
5276:
5227:
5204:
5164:
5080:
5014:
4994:
4941:
4882:
4829:
4809:
4789:
4769:
4749:
4714:
4685:
4650:
4621:
4589:
4569:
4462:i ← 0:s - 1
4385:
4354:
4335:
4315:
4280:
4247:{\displaystyle S'}
4244:
4219:
4146:
4075:
4029:{\displaystyle S'}
4026:
4001:
3981:
3919:
3892:
3852:
3787:
3764:
3687:
3667:
3632:
3603:{\displaystyle B'}
3600:
3575:
3510:
3490:
3454:
3437:{\displaystyle B'}
3434:
3400:
3353:{\displaystyle B'}
3350:
3310:
3246:
3196:
3128:
3108:
3082:
3062:
3033:
3004:
2984:
2949:
2929:
2894:
2851:
2818:
2789:
2759:
2722:
2672:
2652:
2632:
2579:
2559:
2539:
2519:
2484:
2452:
2411:
2378:
2343:
2310:
2290:
2263:
2198:
2171:
2112:
2071:
2036:
2001:
1960:
1921:
1850:
1830:
1798:
1757:
1711:
1661:
1620:
1583:
1517:
1487:
1416:
1395:
1353:
1317:
1283:
1230:
1210:
1190:
1150:
1124:
1104:
1084:
1064:
1037:
1017:
997:
977:
957:
930:
898:
864:
844:
824:
798:
772:
748:
728:
703:{\displaystyle A=}
700:
602:
561:{\displaystyle S=}
558:
500:. For example, if
490:
426:
399:
375:{\displaystyle S=}
372:
295:
257:
219:
172:{\displaystyle A=}
169:
8237:. Springer: 1–23.
8191:{\displaystyle A}
8114:{\displaystyle j}
8094:{\displaystyle i}
8024:{\displaystyle S}
7965:{\displaystyle S}
7945:{\displaystyle S}
7925:{\displaystyle T}
7842:
7776:
7608:{\displaystyle T}
7549:{\displaystyle j}
7529:{\displaystyle i}
7456:{\displaystyle S}
7217:
7102:{\displaystyle 0}
7059:{\displaystyle c}
7039:{\displaystyle A}
7004:{\displaystyle A}
6969:{\displaystyle S}
6949:{\displaystyle c}
6929:{\displaystyle A}
6894:{\displaystyle j}
6842:{\displaystyle i}
6631:{\displaystyle S}
6570:{\displaystyle S}
6445:{\displaystyle s}
6425:{\displaystyle A}
6401:{\displaystyle A}
6287:
6160:{\displaystyle t}
6140:{\displaystyle t}
5950:{\displaystyle B}
5915:{\displaystyle B}
5853:{\displaystyle B}
5791:{\displaystyle B}
5756:{\displaystyle B}
5724:{\displaystyle B}
5608:{\displaystyle x}
5550:{\displaystyle B}
5515:{\displaystyle c}
5468:{\displaystyle c}
5448:{\displaystyle c}
5428:{\displaystyle B}
5279:{\displaystyle S}
5230:{\displaystyle c}
5167:{\displaystyle B}
5083:{\displaystyle B}
5017:{\displaystyle B}
4832:{\displaystyle B}
4812:{\displaystyle A}
4792:{\displaystyle A}
4779:to an answer for
4772:{\displaystyle B}
4752:{\displaystyle A}
4717:{\displaystyle A}
4688:{\displaystyle B}
4653:{\displaystyle B}
4592:{\displaystyle A}
4572:{\displaystyle B}
4357:{\displaystyle s}
4338:{\displaystyle B}
4222:{\displaystyle B}
4078:{\displaystyle S}
4004:{\displaystyle S}
3984:{\displaystyle B}
3790:{\displaystyle s}
3690:{\displaystyle q}
3670:{\displaystyle B}
3635:{\displaystyle B}
3513:{\displaystyle B}
3457:{\displaystyle b}
3131:{\displaystyle A}
3085:{\displaystyle D}
3065:{\displaystyle A}
3036:{\displaystyle B}
3007:{\displaystyle i}
2987:{\displaystyle B}
2932:{\displaystyle D}
2904:be an array, and
2897:{\displaystyle A}
2846:
2787:
2675:{\displaystyle b}
2655:{\displaystyle a}
2582:{\displaystyle c}
2562:{\displaystyle b}
2542:{\displaystyle a}
2522:{\displaystyle A}
2455:{\displaystyle A}
2381:{\displaystyle A}
2313:{\displaystyle c}
2115:{\displaystyle A}
2074:{\displaystyle A}
2046:. Any element of
2039:{\displaystyle A}
2004:{\displaystyle A}
1963:{\displaystyle A}
1915:
1853:{\displaystyle w}
1833:{\displaystyle S}
1813:
1812:
1419:{\displaystyle w}
1390:
1312:
1233:{\displaystyle C}
1213:{\displaystyle b}
1127:{\displaystyle B}
1107:{\displaystyle b}
1087:{\displaystyle B}
1040:{\displaystyle b}
1020:{\displaystyle B}
1007:is not a mode of
1000:{\displaystyle c}
980:{\displaystyle C}
867:{\displaystyle B}
847:{\displaystyle c}
775:{\displaystyle c}
751:{\displaystyle B}
731:{\displaystyle A}
83:Problem statement
69:
68:
61:
8326:
8303:
8302:
8294:
8288:
8287:
8277:
8263:
8253:Krizanc, Danny;
8250:
8239:
8238:
8232:
8223:
8197:
8195:
8194:
8189:
8177:
8175:
8174:
8169:
8167:
8166:
8165:
8164:
8163:
8147:
8146:
8145:
8120:
8118:
8117:
8112:
8100:
8098:
8097:
8092:
8080:
8078:
8077:
8072:
8070:
8069:
8068:
8052:
8051:
8050:
8030:
8028:
8027:
8022:
8017:
8016:
8015:
7999:
7998:
7997:
7971:
7969:
7968:
7963:
7951:
7949:
7948:
7943:
7931:
7929:
7928:
7923:
7911:
7909:
7908:
7903:
7853:
7851:
7850:
7845:
7843:
7841:
7840:
7822:
7817:
7806:
7791:
7789:
7788:
7783:
7781:
7777:
7775:
7774:
7762:
7761:
7760:
7742:
7741:
7731:
7715:
7713:
7712:
7707:
7702:
7701:
7686:
7685:
7684:
7683:
7654:
7653:
7641:
7640:
7614:
7612:
7611:
7606:
7594:
7592:
7591:
7586:
7581:
7580:
7555:
7553:
7552:
7547:
7535:
7533:
7532:
7527:
7515:
7513:
7512:
7507:
7462:
7460:
7459:
7454:
7442:
7440:
7439:
7434:
7429:
7428:
7427:
7426:
7397:
7396:
7374:
7372:
7371:
7366:
7364:
7363:
7362:
7361:
7325:
7323:
7322:
7317:
7315:
7314:
7298:
7296:
7295:
7290:
7288:
7287:
7286:
7266:
7264:
7263:
7258:
7256:
7255:
7254:
7234:
7232:
7231:
7226:
7224:
7223:
7222:
7209:
7195:
7193:
7192:
7187:
7172:
7170:
7169:
7166:{\displaystyle }
7164:
7131:
7129:
7128:
7123:
7108:
7106:
7105:
7100:
7088:
7086:
7085:
7080:
7065:
7063:
7062:
7057:
7045:
7043:
7042:
7037:
7010:
7008:
7007:
7002:
6975:
6973:
6972:
6967:
6955:
6953:
6952:
6947:
6935:
6933:
6932:
6927:
6900:
6898:
6897:
6892:
6880:
6878:
6877:
6872:
6870:
6869:
6868:
6848:
6846:
6845:
6840:
6828:
6826:
6825:
6820:
6818:
6817:
6816:
6796:
6794:
6793:
6788:
6744:
6742:
6741:
6736:
6731:
6730:
6708:
6706:
6705:
6700:
6698:
6697:
6673:
6672:
6654:
6653:
6637:
6635:
6634:
6629:
6602:
6600:
6599:
6594:
6576:
6574:
6573:
6568:
6557:. Build a table
6556:
6554:
6553:
6548:
6540:
6516:
6514:
6513:
6508:
6506:
6505:
6481:
6480:
6468:
6467:
6451:
6449:
6448:
6443:
6431:
6429:
6428:
6423:
6412:Split the array
6407:
6405:
6404:
6399:
6364:
6362:
6361:
6356:
6338:
6336:
6335:
6330:
6325:
6324:
6302:
6300:
6299:
6294:
6292:
6288:
6286:
6285:
6273:
6272:
6271:
6253:
6252:
6242:
6218:
6216:
6215:
6210:
6202:
6166:
6164:
6163:
6158:
6146:
6144:
6143:
6138:
6120:
6118:
6117:
6112:
6110:
6109:
6097:
6096:
6080:
6078:
6077:
6072:
6045:
6043:
6042:
6037:
6035:
6034:
6009:
6007:
6006:
6001:
5993:
5992:
5971:
5956:
5954:
5953:
5948:
5921:
5919:
5918:
5913:
5892:
5890:
5889:
5884:
5882:
5881:
5859:
5857:
5856:
5851:
5824:
5822:
5821:
5816:
5814:
5813:
5797:
5795:
5794:
5789:
5762:
5760:
5759:
5754:
5730:
5728:
5727:
5722:
5689:
5687:
5686:
5681:
5655:
5644:
5643:
5614:
5612:
5611:
5606:
5583:
5581:
5580:
5575:
5573:
5572:
5556:
5554:
5553:
5548:
5521:
5519:
5518:
5513:
5501:
5499:
5498:
5493:
5491:
5490:
5474:
5472:
5471:
5466:
5455:, in which case
5454:
5452:
5451:
5446:
5434:
5432:
5431:
5426:
5399:
5397:
5396:
5391:
5383:
5382:
5366:
5364:
5363:
5358:
5353:
5352:
5340:
5339:
5327:
5312:
5310:
5309:
5304:
5302:
5301:
5285:
5283:
5282:
5277:
5272:
5271:
5259:
5258:
5236:
5234:
5233:
5228:
5213:
5211:
5210:
5205:
5203:
5202:
5190:
5189:
5173:
5171:
5170:
5165:
5127:
5126:
5089:
5087:
5086:
5081:
5064:
5063:
5023:
5021:
5020:
5015:
5003:
5001:
5000:
4995:
4981:
4967:
4966:
4950:
4948:
4947:
4942:
4934:
4908:
4907:
4891:
4889:
4888:
4883:
4838:
4836:
4835:
4830:
4818:
4816:
4815:
4810:
4798:
4796:
4795:
4790:
4778:
4776:
4775:
4770:
4758:
4756:
4755:
4750:
4723:
4721:
4720:
4715:
4694:
4692:
4691:
4686:
4659:
4657:
4656:
4651:
4630:
4628:
4627:
4622:
4599:, since for any
4598:
4596:
4595:
4590:
4578:
4576:
4575:
4570:
4401:computeS_Sprime
4394:
4392:
4391:
4386:
4384:
4363:
4361:
4360:
4355:
4344:
4342:
4341:
4336:
4324:
4322:
4321:
4316:
4289:
4287:
4286:
4281:
4276:
4275:
4253:
4251:
4250:
4245:
4243:
4228:
4226:
4225:
4220:
4203:
4202:
4178:
4177:
4155:
4153:
4152:
4147:
4145:
4144:
4120:
4119:
4101:
4100:
4084:
4082:
4081:
4076:
4071:
4070:
4058:
4057:
4035:
4033:
4032:
4027:
4025:
4010:
4008:
4007:
4002:
3990:
3988:
3987:
3982:
3928:
3926:
3925:
3920:
3918:
3917:
3902:. Thus, a block
3901:
3899:
3898:
3893:
3885:
3861:
3859:
3858:
3853:
3851:
3850:
3826:
3825:
3813:
3812:
3796:
3794:
3793:
3788:
3773:
3771:
3770:
3765:
3733:
3722:
3721:
3696:
3694:
3693:
3688:
3676:
3674:
3673:
3668:
3641:
3639:
3638:
3633:
3609:
3607:
3606:
3601:
3599:
3584:
3582:
3581:
3576:
3574:
3573:
3549:
3548:
3536:
3535:
3519:
3517:
3516:
3511:
3499:
3497:
3496:
3491:
3489:
3488:
3463:
3461:
3460:
3455:
3443:
3441:
3440:
3435:
3424:
3409:
3407:
3406:
3401:
3359:
3357:
3356:
3351:
3334:
3319:
3317:
3316:
3311:
3287:
3272:
3271:
3255:
3253:
3252:
3247:
3205:
3203:
3202:
3197:
3195:
3194:
3170:
3169:
3157:
3156:
3137:
3135:
3134:
3129:
3117:
3115:
3114:
3109:
3091:
3089:
3088:
3083:
3071:
3069:
3068:
3063:
3042:
3040:
3039:
3034:
3013:
3011:
3010:
3005:
2993:
2991:
2990:
2985:
2958:
2956:
2955:
2950:
2938:
2936:
2935:
2930:
2903:
2901:
2900:
2895:
2860:
2858:
2857:
2852:
2847:
2842:
2827:
2825:
2824:
2819:
2798:
2796:
2795:
2790:
2788:
2783:
2768:
2766:
2765:
2760:
2752:
2731:
2729:
2728:
2723:
2718:
2717:
2681:
2679:
2678:
2673:
2661:
2659:
2658:
2653:
2641:
2639:
2638:
2633:
2588:
2586:
2585:
2580:
2568:
2566:
2565:
2560:
2548:
2546:
2545:
2540:
2528:
2526:
2525:
2520:
2493:
2491:
2490:
2485:
2461:
2459:
2458:
2453:
2420:
2418:
2417:
2412:
2404:
2403:
2387:
2385:
2384:
2379:
2352:
2350:
2349:
2344:
2336:
2335:
2319:
2317:
2316:
2311:
2299:
2297:
2296:
2291:
2289:
2288:
2272:
2270:
2269:
2264:
2207:
2205:
2204:
2199:
2197:
2196:
2180:
2178:
2177:
2172:
2121:
2119:
2118:
2113:
2080:
2078:
2077:
2072:
2045:
2043:
2042:
2037:
2010:
2008:
2007:
2002:
1970:and the mode of
1969:
1967:
1966:
1961:
1930:
1928:
1927:
1922:
1920:
1916:
1914:
1907:
1886:
1875:
1860:bits each needs
1859:
1857:
1856:
1851:
1839:
1837:
1836:
1831:
1807:
1805:
1804:
1799:
1794:
1766:
1764:
1763:
1758:
1744:
1743:
1720:
1718:
1717:
1712:
1707:
1706:
1670:
1668:
1667:
1662:
1657:
1629:
1627:
1626:
1621:
1616:
1615:
1592:
1590:
1589:
1584:
1570:
1565:
1564:
1526:
1524:
1523:
1518:
1496:
1494:
1493:
1488:
1474:
1454:
1453:
1426:is the word size
1425:
1423:
1422:
1417:
1404:
1402:
1401:
1396:
1391:
1386:
1378:
1362:
1360:
1359:
1354:
1326:
1324:
1323:
1318:
1313:
1308:
1292:
1290:
1289:
1284:
1248:
1239:
1237:
1236:
1231:
1219:
1217:
1216:
1211:
1199:
1197:
1196:
1191:
1189:
1188:
1176:
1175:
1159:
1157:
1156:
1151:
1133:
1131:
1130:
1125:
1113:
1111:
1110:
1105:
1093:
1091:
1090:
1085:
1073:
1071:
1070:
1065:
1063:
1062:
1046:
1044:
1043:
1038:
1026:
1024:
1023:
1018:
1006:
1004:
1003:
998:
986:
984:
983:
978:
966:
964:
963:
958:
956:
955:
939:
937:
936:
931:
907:
905:
904:
899:
873:
871:
870:
865:
853:
851:
850:
845:
833:
831:
830:
825:
807:
805:
804:
799:
781:
779:
778:
773:
757:
755:
754:
749:
737:
735:
734:
729:
709:
707:
706:
701:
696:
695:
671:
670:
652:
651:
611:
609:
608:
603:
567:
565:
564:
559:
499:
497:
496:
491:
452:
451:
435:
433:
432:
427:
425:
424:
408:
406:
405:
400:
398:
397:
381:
379:
378:
373:
368:
367:
343:
342:
330:
329:
304:
302:
301:
296:
266:
264:
263:
258:
228:
226:
225:
220:
178:
176:
175:
170:
165:
164:
140:
139:
127:
126:
64:
57:
53:
50:
44:
24:
23:
16:
8334:
8333:
8329:
8328:
8327:
8325:
8324:
8323:
8309:
8308:
8307:
8306:
8296:
8295:
8291:
8261:
8252:
8251:
8242:
8230:
8225:
8224:
8209:
8204:
8180:
8179:
8156:
8151:
8138:
8133:
8128:
8123:
8122:
8103:
8102:
8083:
8082:
8061:
8056:
8043:
8038:
8033:
8032:
8008:
8003:
7990:
7985:
7974:
7973:
7954:
7953:
7934:
7933:
7914:
7913:
7864:
7863:
7860:
7794:
7793:
7763:
7733:
7732:
7726:
7718:
7717:
7693:
7675:
7670:
7645:
7632:
7621:
7620:
7597:
7596:
7572:
7558:
7557:
7538:
7537:
7518:
7517:
7468:
7467:
7445:
7444:
7418:
7413:
7388:
7377:
7376:
7353:
7348:
7328:
7327:
7306:
7301:
7300:
7279:
7274:
7269:
7268:
7247:
7242:
7237:
7236:
7204:
7198:
7197:
7175:
7174:
7134:
7133:
7111:
7110:
7091:
7090:
7068:
7067:
7048:
7047:
7013:
7012:
6978:
6977:
6958:
6957:
6938:
6937:
6903:
6902:
6883:
6882:
6861:
6856:
6851:
6850:
6831:
6830:
6809:
6804:
6799:
6798:
6749:
6748:
6722:
6711:
6710:
6689:
6658:
6645:
6640:
6639:
6638:is the mode of
6605:
6604:
6579:
6578:
6559:
6558:
6519:
6518:
6497:
6472:
6459:
6454:
6453:
6434:
6433:
6414:
6413:
6375:
6374:
6371:
6341:
6340:
6316:
6305:
6304:
6274:
6244:
6243:
6237:
6229:
6228:
6225:
6169:
6168:
6149:
6148:
6129:
6128:
6101:
6088:
6083:
6082:
6048:
6047:
6017:
6012:
6011:
5984:
5964:
5959:
5958:
5924:
5923:
5895:
5894:
5873:
5868:
5867:
5827:
5826:
5805:
5800:
5799:
5765:
5764:
5736:
5735:
5692:
5691:
5648:
5626:
5621:
5620:
5597:
5596:
5590:
5584:its frequency.
5564:
5559:
5558:
5524:
5523:
5504:
5503:
5482:
5477:
5476:
5457:
5456:
5437:
5436:
5402:
5401:
5374:
5369:
5368:
5344:
5331:
5320:
5315:
5314:
5293:
5288:
5287:
5263:
5250:
5239:
5238:
5219:
5218:
5194:
5181:
5176:
5175:
5118:
5092:
5091:
5055:
5026:
5025:
5006:
5005:
4958:
4953:
4952:
4899:
4894:
4893:
4844:
4843:
4821:
4820:
4801:
4800:
4781:
4780:
4761:
4760:
4726:
4725:
4697:
4696:
4695:if and only if
4662:
4661:
4633:
4632:
4601:
4600:
4581:
4580:
4561:
4560:
4557:
4552:
4377:
4366:
4365:
4346:
4345:
4327:
4326:
4292:
4291:
4267:
4256:
4255:
4236:
4231:
4230:
4194:
4169:
4158:
4157:
4136:
4105:
4092:
4087:
4086:
4085:is the mode of
4062:
4049:
4038:
4037:
4018:
4013:
4012:
3993:
3992:
3931:
3930:
3909:
3904:
3903:
3864:
3863:
3862:, each of size
3842:
3817:
3804:
3799:
3798:
3779:
3778:
3726:
3704:
3699:
3698:
3679:
3678:
3644:
3643:
3615:
3614:
3592:
3587:
3586:
3565:
3540:
3527:
3522:
3521:
3502:
3501:
3471:
3466:
3465:
3446:
3445:
3417:
3412:
3411:
3362:
3361:
3327:
3322:
3321:
3263:
3258:
3257:
3208:
3207:
3186:
3161:
3148:
3143:
3142:
3120:
3119:
3094:
3093:
3074:
3073:
3045:
3044:
3016:
3015:
2996:
2995:
2961:
2960:
2941:
2940:
2906:
2905:
2871:
2870:
2867:
2830:
2829:
2801:
2800:
2771:
2770:
2734:
2733:
2709:
2692:
2691:
2688:
2664:
2663:
2644:
2643:
2591:
2590:
2571:
2570:
2551:
2550:
2531:
2530:
2496:
2495:
2464:
2463:
2423:
2422:
2395:
2390:
2389:
2355:
2354:
2327:
2322:
2321:
2320:with frequency
2302:
2301:
2280:
2275:
2274:
2210:
2209:
2188:
2183:
2182:
2124:
2123:
2083:
2082:
2048:
2047:
2013:
2012:
1972:
1971:
1937:
1936:
1887:
1876:
1870:
1862:
1861:
1842:
1841:
1822:
1821:
1818:
1770:
1769:
1735:
1724:
1723:
1689:
1678:
1677:
1633:
1632:
1607:
1596:
1595:
1547:
1536:
1535:
1500:
1499:
1445:
1434:
1433:
1408:
1407:
1366:
1365:
1336:
1335:
1296:
1295:
1266:
1265:
1246:
1222:
1221:
1202:
1201:
1180:
1167:
1162:
1161:
1136:
1135:
1116:
1115:
1114:is the mode of
1096:
1095:
1076:
1075:
1054:
1049:
1048:
1047:with frequency
1029:
1028:
1009:
1008:
989:
988:
987:. Suppose that
969:
968:
947:
942:
941:
910:
909:
884:
883:
880:
856:
855:
836:
835:
810:
809:
784:
783:
764:
763:
740:
739:
720:
719:
716:
687:
656:
643:
614:
613:
570:
569:
502:
501:
443:
438:
437:
416:
411:
410:
389:
384:
383:
359:
334:
321:
307:
306:
269:
268:
231:
230:
181:
180:
156:
131:
118:
89:
88:
87:Given an array
85:
73:data structures
65:
54:
48:
45:
37:help improve it
34:
25:
21:
12:
11:
5:
8332:
8330:
8322:
8321:
8311:
8310:
8305:
8304:
8289:
8240:
8206:
8205:
8203:
8200:
8187:
8162:
8159:
8154:
8150:
8144:
8141:
8136:
8131:
8110:
8090:
8067:
8064:
8059:
8055:
8049:
8046:
8041:
8020:
8014:
8011:
8006:
8002:
7996:
7993:
7988:
7984:
7981:
7961:
7941:
7921:
7901:
7898:
7895:
7892:
7889:
7886:
7883:
7880:
7877:
7874:
7871:
7862:Given a query
7859:
7856:
7839:
7835:
7832:
7828:
7825:
7821:
7816:
7812:
7809:
7804:
7801:
7780:
7773:
7769:
7766:
7759:
7755:
7752:
7748:
7745:
7740:
7736:
7729:
7725:
7705:
7700:
7696:
7692:
7689:
7682:
7678:
7673:
7669:
7666:
7663:
7660:
7657:
7652:
7648:
7644:
7639:
7635:
7631:
7628:
7617:
7616:
7604:
7584:
7579:
7575:
7571:
7568:
7565:
7545:
7525:
7505:
7502:
7499:
7496:
7493:
7490:
7487:
7484:
7481:
7478:
7475:
7464:
7452:
7432:
7425:
7421:
7416:
7412:
7409:
7406:
7403:
7400:
7395:
7391:
7387:
7384:
7360:
7356:
7351:
7347:
7344:
7341:
7338:
7335:
7313:
7309:
7285:
7282:
7277:
7253:
7250:
7245:
7221:
7216:
7213:
7208:
7185:
7182:
7162:
7159:
7156:
7153:
7150:
7147:
7144:
7141:
7121:
7118:
7098:
7078:
7075:
7055:
7035:
7032:
7029:
7026:
7023:
7020:
7000:
6997:
6994:
6991:
6988:
6985:
6965:
6945:
6925:
6922:
6919:
6916:
6913:
6910:
6890:
6867:
6864:
6859:
6838:
6815:
6812:
6807:
6786:
6783:
6780:
6777:
6774:
6771:
6768:
6765:
6762:
6759:
6756:
6747:For any query
6745:
6734:
6729:
6725:
6721:
6718:
6696:
6692:
6688:
6685:
6682:
6679:
6676:
6671:
6668:
6665:
6661:
6657:
6652:
6648:
6627:
6624:
6621:
6618:
6615:
6612:
6592:
6589:
6586:
6566:
6546:
6543:
6539:
6535:
6532:
6529:
6526:
6504:
6500:
6496:
6493:
6490:
6487:
6484:
6479:
6475:
6471:
6466:
6462:
6441:
6421:
6397:
6394:
6391:
6388:
6385:
6382:
6370:
6367:
6354:
6351:
6348:
6328:
6323:
6319:
6315:
6312:
6291:
6284:
6280:
6277:
6270:
6266:
6263:
6259:
6256:
6251:
6247:
6240:
6236:
6224:
6221:
6208:
6205:
6201:
6197:
6194:
6191:
6188:
6185:
6182:
6179:
6176:
6156:
6136:
6125:
6124:
6123:
6122:
6108:
6104:
6100:
6095:
6091:
6070:
6067:
6064:
6061:
6058:
6055:
6033:
6030:
6027:
6024:
6020:
5999:
5996:
5991:
5987:
5983:
5980:
5977:
5974:
5970:
5967:
5946:
5943:
5940:
5937:
5934:
5931:
5911:
5908:
5905:
5902:
5880:
5876:
5864:
5849:
5846:
5843:
5840:
5837:
5834:
5812:
5808:
5787:
5784:
5781:
5778:
5775:
5772:
5752:
5749:
5746:
5743:
5732:
5720:
5717:
5714:
5711:
5708:
5705:
5702:
5699:
5679:
5676:
5673:
5670:
5667:
5664:
5661:
5658:
5654:
5651:
5647:
5642:
5639:
5636:
5633:
5629:
5604:
5589:
5586:
5571:
5567:
5546:
5543:
5540:
5537:
5534:
5531:
5511:
5489:
5485:
5464:
5444:
5424:
5421:
5418:
5415:
5412:
5409:
5389:
5386:
5381:
5377:
5356:
5351:
5347:
5343:
5338:
5334:
5330:
5326:
5323:
5300:
5296:
5275:
5270:
5266:
5262:
5257:
5253:
5249:
5246:
5226:
5201:
5197:
5193:
5188:
5184:
5163:
5160:
5157:
5154:
5151:
5148:
5145:
5142:
5139:
5136:
5133:
5130:
5125:
5121:
5117:
5114:
5111:
5108:
5105:
5102:
5099:
5079:
5076:
5073:
5070:
5067:
5062:
5058:
5054:
5051:
5048:
5045:
5042:
5039:
5036:
5033:
5013:
4993:
4990:
4987:
4984:
4980:
4976:
4973:
4970:
4965:
4961:
4940:
4937:
4933:
4929:
4926:
4923:
4920:
4917:
4914:
4911:
4906:
4902:
4881:
4878:
4875:
4872:
4869:
4866:
4863:
4860:
4857:
4854:
4851:
4842:Given a query
4828:
4808:
4788:
4768:
4748:
4745:
4742:
4739:
4736:
4733:
4724:is a mode for
4713:
4710:
4707:
4704:
4684:
4681:
4678:
4675:
4672:
4669:
4660:is a mode for
4649:
4646:
4643:
4640:
4620:
4617:
4614:
4611:
4608:
4588:
4568:
4556:
4553:
4523:j = block_end
4441:firstOccurence
4397:
4383:
4380:
4376:
4373:
4353:
4334:
4314:
4311:
4308:
4305:
4302:
4299:
4279:
4274:
4270:
4266:
4263:
4242:
4239:
4218:
4215:
4212:
4209:
4206:
4201:
4197:
4193:
4190:
4187:
4184:
4181:
4176:
4172:
4168:
4165:
4143:
4139:
4135:
4132:
4129:
4126:
4123:
4118:
4115:
4112:
4108:
4104:
4099:
4095:
4074:
4069:
4065:
4061:
4056:
4052:
4048:
4045:
4024:
4021:
4000:
3980:
3977:
3974:
3971:
3968:
3965:
3962:
3959:
3956:
3953:
3950:
3947:
3944:
3941:
3938:
3916:
3912:
3891:
3888:
3884:
3880:
3877:
3874:
3871:
3849:
3845:
3841:
3838:
3835:
3832:
3829:
3824:
3820:
3816:
3811:
3807:
3786:
3763:
3760:
3757:
3754:
3751:
3748:
3745:
3742:
3739:
3736:
3732:
3729:
3725:
3720:
3717:
3714:
3711:
3707:
3686:
3666:
3663:
3660:
3657:
3654:
3651:
3631:
3628:
3625:
3622:
3598:
3595:
3572:
3568:
3564:
3561:
3558:
3555:
3552:
3547:
3543:
3539:
3534:
3530:
3509:
3487:
3484:
3481:
3478:
3474:
3453:
3433:
3430:
3427:
3423:
3420:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3375:
3372:
3369:
3349:
3346:
3343:
3340:
3337:
3333:
3330:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3286:
3281:
3278:
3275:
3270:
3266:
3245:
3242:
3239:
3236:
3233:
3230:
3227:
3224:
3221:
3218:
3215:
3193:
3189:
3185:
3182:
3179:
3176:
3173:
3168:
3164:
3160:
3155:
3151:
3127:
3107:
3104:
3101:
3081:
3061:
3058:
3055:
3052:
3032:
3029:
3026:
3023:
3003:
2983:
2980:
2977:
2974:
2971:
2968:
2948:
2928:
2925:
2922:
2919:
2916:
2913:
2893:
2890:
2887:
2884:
2881:
2878:
2866:
2863:
2850:
2845:
2840:
2837:
2817:
2814:
2811:
2808:
2786:
2781:
2778:
2758:
2755:
2751:
2747:
2744:
2741:
2721:
2716:
2712:
2708:
2705:
2702:
2699:
2687:
2684:
2671:
2651:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2578:
2569:, which makes
2558:
2538:
2518:
2515:
2512:
2509:
2506:
2503:
2483:
2480:
2477:
2474:
2471:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2410:
2407:
2402:
2398:
2388:and frequency
2377:
2374:
2371:
2368:
2365:
2362:
2342:
2339:
2334:
2330:
2309:
2287:
2283:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2195:
2191:
2170:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2070:
2067:
2064:
2061:
2058:
2055:
2035:
2032:
2029:
2026:
2023:
2020:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1959:
1956:
1953:
1950:
1947:
1944:
1919:
1913:
1910:
1906:
1902:
1899:
1896:
1893:
1890:
1885:
1882:
1879:
1873:
1869:
1849:
1829:
1817:
1814:
1811:
1810:
1808:
1797:
1793:
1789:
1786:
1783:
1780:
1777:
1767:
1756:
1753:
1750:
1747:
1742:
1738:
1734:
1731:
1721:
1710:
1705:
1702:
1699:
1696:
1692:
1688:
1685:
1674:
1673:
1671:
1660:
1656:
1652:
1649:
1646:
1643:
1640:
1630:
1619:
1614:
1610:
1606:
1603:
1593:
1582:
1579:
1576:
1573:
1569:
1563:
1560:
1557:
1554:
1550:
1546:
1543:
1532:
1531:
1529:
1527:
1516:
1513:
1510:
1507:
1497:
1486:
1483:
1480:
1477:
1473:
1469:
1466:
1463:
1460:
1457:
1452:
1448:
1444:
1441:
1430:
1429:
1427:
1415:
1405:
1394:
1389:
1385:
1381:
1376:
1373:
1363:
1352:
1349:
1346:
1343:
1332:
1331:
1329:
1327:
1316:
1311:
1306:
1303:
1293:
1282:
1279:
1276:
1273:
1262:
1261:
1258:
1255:
1252:
1245:
1242:
1229:
1209:
1187:
1183:
1179:
1174:
1170:
1149:
1146:
1143:
1123:
1103:
1083:
1061:
1057:
1036:
1016:
996:
976:
954:
950:
929:
926:
923:
920:
917:
897:
894:
891:
879:
876:
863:
843:
823:
820:
817:
797:
794:
791:
771:
747:
727:
715:
712:
699:
694:
690:
686:
683:
680:
677:
674:
669:
666:
663:
659:
655:
650:
646:
642:
639:
636:
633:
630:
627:
624:
621:
601:
598:
595:
592:
589:
586:
583:
580:
577:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
450:
446:
423:
419:
396:
392:
382:is an element
371:
366:
362:
358:
355:
352:
349:
346:
341:
337:
333:
328:
324:
320:
317:
314:
294:
291:
288:
285:
282:
279:
276:
256:
253:
250:
247:
244:
241:
238:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
168:
163:
159:
155:
152:
149:
146:
143:
138:
134:
130:
125:
121:
117:
114:
111:
108:
105:
102:
99:
96:
84:
81:
67:
66:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
8331:
8320:
8317:
8316:
8314:
8300:
8293:
8290:
8285:
8281:
8276:
8271:
8267:
8260:
8256:
8249:
8247:
8245:
8241:
8236:
8229:
8222:
8220:
8218:
8216:
8214:
8212:
8208:
8201:
8199:
8185:
8160:
8157:
8152:
8148:
8142:
8139:
8134:
8129:
8108:
8088:
8065:
8062:
8057:
8053:
8047:
8044:
8039:
8012:
8009:
8004:
8000:
7994:
7991:
7986:
7979:
7959:
7939:
7919:
7896:
7893:
7890:
7887:
7884:
7878:
7875:
7872:
7869:
7857:
7855:
7837:
7833:
7830:
7826:
7823:
7819:
7814:
7810:
7807:
7802:
7799:
7778:
7771:
7767:
7764:
7757:
7753:
7750:
7746:
7743:
7738:
7734:
7727:
7723:
7698:
7694:
7690:
7687:
7680:
7676:
7667:
7664:
7661:
7658:
7650:
7646:
7642:
7637:
7633:
7626:
7615:of this size.
7602:
7577:
7573:
7569:
7563:
7543:
7523:
7500:
7497:
7494:
7491:
7488:
7482:
7479:
7476:
7473:
7465:
7450:
7423:
7419:
7410:
7407:
7404:
7401:
7393:
7389:
7382:
7358:
7354:
7345:
7342:
7339:
7336:
7311:
7307:
7283:
7280:
7275:
7251:
7248:
7243:
7214:
7211:
7183:
7180:
7157:
7154:
7151:
7148:
7145:
7142:
7119:
7116:
7096:
7076:
7073:
7053:
7030:
7027:
7024:
7018:
6995:
6992:
6989:
6983:
6963:
6943:
6920:
6917:
6914:
6908:
6888:
6865:
6862:
6857:
6836:
6813:
6810:
6805:
6781:
6778:
6775:
6772:
6769:
6763:
6760:
6757:
6754:
6746:
6727:
6723:
6716:
6694:
6690:
6686:
6683:
6680:
6677:
6674:
6669:
6666:
6663:
6659:
6655:
6650:
6646:
6622:
6619:
6616:
6610:
6590:
6587:
6584:
6564:
6541:
6537:
6533:
6527:
6524:
6502:
6498:
6494:
6491:
6488:
6485:
6482:
6477:
6473:
6469:
6464:
6460:
6439:
6419:
6411:
6410:
6409:
6392:
6389:
6386:
6380:
6369:Preprocessing
6368:
6366:
6352:
6349:
6346:
6321:
6317:
6310:
6289:
6282:
6278:
6275:
6268:
6264:
6261:
6257:
6254:
6249:
6245:
6238:
6234:
6222:
6220:
6203:
6199:
6195:
6189:
6186:
6180:
6174:
6154:
6134:
6106:
6102:
6098:
6093:
6089:
6065:
6059:
6056:
6053:
6028:
6022:
6018:
5997:
5994:
5989:
5985:
5981:
5975:
5968:
5965:
5941:
5938:
5935:
5929:
5906:
5900:
5878:
5874:
5865:
5862:
5861:
5844:
5841:
5838:
5832:
5810:
5806:
5782:
5779:
5776:
5770:
5747:
5741:
5733:
5715:
5712:
5709:
5706:
5703:
5697:
5677:
5674:
5668:
5665:
5659:
5652:
5649:
5637:
5631:
5627:
5618:
5617:
5616:
5602:
5593:
5587:
5585:
5569:
5565:
5541:
5538:
5535:
5529:
5509:
5487:
5483:
5462:
5442:
5419:
5416:
5413:
5407:
5387:
5384:
5379:
5375:
5349:
5345:
5341:
5336:
5332:
5324:
5321:
5298:
5294:
5268:
5264:
5260:
5255:
5251:
5244:
5224:
5215:
5199:
5195:
5191:
5186:
5182:
5158:
5155:
5149:
5146:
5143:
5140:
5137:
5131:
5128:
5123:
5119:
5109:
5106:
5103:
5097:
5071:
5068:
5065:
5060:
5056:
5049:
5046:
5043:
5040:
5037:
5031:
5011:
4991:
4988:
4982:
4978:
4974:
4968:
4963:
4959:
4935:
4931:
4924:
4921:
4918:
4909:
4904:
4900:
4876:
4873:
4870:
4867:
4864:
4858:
4855:
4852:
4849:
4840:
4826:
4806:
4786:
4766:
4743:
4740:
4737:
4731:
4708:
4702:
4679:
4676:
4673:
4667:
4644:
4638:
4618:
4615:
4612:
4609:
4606:
4586:
4566:
4554:
4551:
4548:
4544:
4540:
4536:
4533:
4530:
4526:
4522:
4519:
4515:
4511:
4508:
4504:
4500:
4497:
4493:
4489:
4485:
4481:
4477:
4473:
4469:
4465:
4461:
4458:
4454:
4450:
4446:
4442:
4438:
4434:
4430:
4426:
4422:
4419:
4415:
4411:
4407:
4404:
4400:
4396:
4381:
4378:
4374:
4371:
4351:
4332:
4309:
4306:
4303:
4297:
4272:
4268:
4261:
4240:
4237:
4213:
4207:
4204:
4199:
4195:
4188:
4185:
4182:
4179:
4174:
4170:
4163:
4141:
4137:
4133:
4130:
4127:
4124:
4121:
4116:
4113:
4110:
4106:
4102:
4097:
4093:
4067:
4063:
4059:
4054:
4050:
4043:
4022:
4019:
3998:
3975:
3969:
3966:
3963:
3957:
3954:
3951:
3948:
3945:
3942:
3936:
3914:
3910:
3886:
3882:
3878:
3872:
3869:
3847:
3843:
3839:
3836:
3833:
3830:
3827:
3822:
3818:
3814:
3809:
3805:
3784:
3775:
3761:
3758:
3752:
3749:
3746:
3743:
3737:
3730:
3727:
3715:
3709:
3705:
3684:
3661:
3658:
3655:
3649:
3626:
3620:
3611:
3596:
3593:
3566:
3562:
3559:
3556:
3553:
3550:
3545:
3541:
3537:
3532:
3528:
3507:
3482:
3476:
3472:
3451:
3428:
3421:
3418:
3394:
3391:
3388:
3385:
3382:
3379:
3376:
3370:
3367:
3344:
3341:
3338:
3331:
3328:
3304:
3301:
3295:
3289:
3279:
3273:
3268:
3264:
3237:
3234:
3231:
3228:
3225:
3222:
3216:
3213:
3187:
3183:
3180:
3177:
3174:
3171:
3166:
3162:
3158:
3153:
3149:
3139:
3125:
3105:
3102:
3099:
3079:
3056:
3050:
3027:
3021:
3001:
2978:
2975:
2972:
2966:
2920:
2917:
2911:
2888:
2885:
2882:
2876:
2865:Preprocessing
2864:
2862:
2843:
2835:
2812:
2806:
2784:
2779:
2776:
2753:
2749:
2745:
2739:
2714:
2710:
2706:
2703:
2697:
2685:
2683:
2669:
2649:
2623:
2620:
2617:
2611:
2605:
2602:
2599:
2596:
2576:
2556:
2536:
2513:
2510:
2507:
2501:
2481:
2478:
2475:
2472:
2469:
2446:
2443:
2440:
2437:
2434:
2428:
2408:
2405:
2400:
2396:
2372:
2369:
2366:
2360:
2340:
2337:
2332:
2328:
2307:
2285:
2281:
2260:
2257:
2248:
2245:
2242:
2239:
2236:
2230:
2224:
2221:
2218:
2215:
2193:
2189:
2168:
2165:
2156:
2153:
2150:
2144:
2138:
2135:
2132:
2129:
2106:
2103:
2100:
2097:
2094:
2088:
2065:
2062:
2059:
2053:
2030:
2027:
2024:
2018:
1995:
1992:
1989:
1986:
1983:
1977:
1954:
1951:
1948:
1942:
1932:
1917:
1908:
1904:
1900:
1897:
1891:
1888:
1883:
1880:
1877:
1871:
1847:
1827:
1815:
1809:
1795:
1791:
1787:
1784:
1781:
1778:
1775:
1768:
1751:
1748:
1745:
1740:
1736:
1729:
1722:
1703:
1700:
1697:
1694:
1690:
1683:
1676:
1675:
1672:
1658:
1654:
1650:
1647:
1644:
1641:
1638:
1631:
1612:
1608:
1601:
1594:
1577:
1574:
1571:
1567:
1561:
1558:
1555:
1552:
1548:
1541:
1534:
1533:
1530:
1528:
1511:
1505:
1498:
1481:
1478:
1475:
1471:
1467:
1464:
1461:
1458:
1455:
1450:
1446:
1439:
1432:
1431:
1428:
1413:
1406:
1387:
1383:
1379:
1371:
1364:
1347:
1341:
1334:
1333:
1330:
1328:
1309:
1301:
1294:
1277:
1271:
1264:
1263:
1259:
1256:
1253:
1250:
1249:
1243:
1241:
1227:
1207:
1185:
1181:
1177:
1172:
1168:
1147:
1144:
1141:
1121:
1101:
1081:
1059:
1055:
1034:
1014:
994:
974:
952:
948:
927:
924:
921:
918:
915:
908:be a mode of
895:
892:
889:
877:
875:
861:
854:is a mode of
841:
821:
818:
815:
795:
792:
789:
782:is a mode of
769:
761:
745:
725:
713:
711:
692:
688:
684:
681:
678:
675:
672:
667:
664:
661:
657:
653:
648:
644:
637:
631:
628:
625:
619:
599:
596:
590:
584:
581:
578:
575:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
510:
507:
484:
481:
478:
475:
472:
469:
466:
460:
457:
448:
444:
421:
417:
394:
390:
364:
360:
356:
353:
350:
347:
344:
339:
335:
331:
326:
322:
315:
312:
305:of any array
289:
283:
280:
277:
274:
254:
251:
248:
245:
242:
239:
236:
213:
210:
207:
204:
201:
195:
192:
189:
186:
161:
157:
153:
150:
147:
144:
141:
136:
132:
128:
123:
119:
112:
106:
103:
100:
94:
82:
80:
78:
74:
63:
60:
52:
42:
38:
32:
29:This article
27:
18:
17:
8298:
8292:
8265:
8234:
7972:at position
7861:
7618:
6372:
6226:
6126:
5798:is at least
5594:
5591:
5216:
4841:
4558:
4549:
4546:
4542:
4538:
4534:
4531:
4528:
4524:
4520:
4517:
4513:
4509:
4506:
4502:
4498:
4495:
4491:
4487:
4483:
4479:
4475:
4471:
4467:
4463:
4459:
4456:
4452:
4448:
4444:
4440:
4436:
4432:
4428:
4424:
4420:
4417:
4413:
4409:
4405:
4402:
4398:
4325:by scanning
3776:
3612:
3140:
2868:
2689:
1933:
1819:
1257:Restrictions
881:
717:
86:
70:
55:
46:
30:
8268:: 517–526.
7792:if we take
6936:. The mode
4484:block_start
3929:spans over
1816:Lower bound
267:. The mode
8301:: 605–616.
8275:cs/0307034
8255:Morin, Pat
8202:References
2732:space and
1254:Query Time
49:April 2014
7834:
7827:
7811:
7768:
7754:
7747:
7155:−
6687:∪
6675:∪
6656:∪
6588:×
6545:⌉
6531:⌈
6279:
6265:
6258:
5995:−
5713:−
5675:≥
5666:−
4989:−
4986:⌋
4972:⌊
4939:⌉
4922:−
4913:⌈
4532:end while
4494:j < n
4488:block_end
4399:algorithm
4307:⋅
4134:∪
4122:∪
4103:∪
3946:⋅
3890:⌉
3876:⌈
3759:≤
3750:−
3677:at least
3571:Δ
3371:∈
3241:Δ
3217:∈
3192:Δ
3092:. Arrays
2947:Δ
2924:Δ
2799:, we get
2406:−
2338:−
1892:
1881:
1868:Ω
1840:cells of
1785:≤
1782:ϵ
1779:≤
1749:
1741:ϵ
1704:ϵ
1698:−
1648:≤
1645:ϵ
1642:≤
1613:ϵ
1575:
1562:ϵ
1556:−
1479:
1465:
1459:
1145:∉
1134:and that
925:∪
893:∉
819:∉
793:∪
760:multisets
714:Theorem 1
461:∈
455:∀
252:≤
246:≤
240:≤
8313:Category
8161:′
8143:′
8066:′
8048:′
8031:, where
8013:′
7995:′
7284:′
7252:′
7132:, where
6866:′
6814:′
6577:of size
5969:′
5653:′
5325:′
4382:′
4241:′
4023:′
3731:′
3597:′
3422:′
3332:′
2479:≠
2473:≠
1200:. Thus,
1094:. Since
229:, where
8280:Bibcode
6452:blocks
4550:end for
4547:end for
4535:for all
4480:noBlock
4457:end for
4445:for all
4423:Tables
4421:output:
3797:blocks
3141:Arrays
1260:Source
1244:Results
1160:, then
834:, then
758:be any
568:, then
35:Please
8319:Arrays
7516:where
6797:, let
6603:where
6046:. Set
5286:. Let
4529:end if
4518:end if
4507:end if
4437:Sprime
4429:Sprime
4408:Array
4406:input:
4229:, and
2208:, and
8270:arXiv
8266:ISAAC
8262:(PDF)
8231:(PDF)
7858:Query
4555:Query
4492:while
2642:than
1251:Space
878:Proof
762:. If
8101:and
7536:and
7267:and
6849:and
6373:Let
6081:and
5595:Let
5557:and
5475:and
5192:<
4951:and
4525:then
4514:then
4503:then
4466:let
4431:let
4427:and
4011:and
3585:and
2869:Let
2828:and
2549:and
1178:>
940:and
882:Let
808:and
738:and
718:Let
77:mode
7831:log
7824:log
7808:log
7765:log
7751:log
7744:log
7109:to
6432:in
6276:log
6262:log
6255:log
5922:in
5893:of
5860:).
5763:in
5619:If
4819:or
4460:for
3642:in
3464:in
3072:in
2662:or
2421:in
2353:in
2081:or
1889:log
1878:log
1746:log
1572:log
1476:log
1462:log
1456:log
71:In
39:to
8315::
8278:.
8264:.
8243:^
8233:.
8210:^
7854:.
6365:.
6219:.
6099::=
6057::=
5214:.
4631:,
4543:do
4539:in
4537:j
4521:if
4510:if
4499:if
4496:do
4476:fc
4464:do
4453:do
4449:in
4447:i
4403:is
4036:.
3774:.
3610:.
3410:,
3256:,
3138:.
3014:,
2682:.
2462:.
874:.
710:.
8286:.
8282::
8272::
8186:A
8158:j
8153:b
8149:,
8140:i
8135:b
8130:U
8109:j
8089:i
8063:j
8058:b
8054:,
8045:i
8040:b
8019:]
8010:j
8005:b
8001:,
7992:i
7987:b
7983:[
7980:S
7960:S
7940:S
7920:T
7900:)
7897:j
7894:,
7891:i
7888:,
7885:A
7882:(
7879:e
7876:d
7873:o
7870:m
7838:n
7820:/
7815:n
7803:=
7800:t
7779:)
7772:n
7758:n
7739:2
7735:n
7728:(
7724:O
7704:)
7699:2
7695:t
7691:s
7688:+
7681:2
7677:t
7672:)
7668:1
7665:+
7662:t
7659:2
7656:(
7651:2
7647:t
7643:+
7638:2
7634:s
7630:(
7627:O
7603:T
7583:)
7578:2
7574:t
7570:s
7567:(
7564:O
7544:j
7524:i
7504:)
7501:j
7498:,
7495:i
7492:,
7489:A
7486:(
7483:e
7480:d
7477:o
7474:m
7451:S
7431:)
7424:2
7420:t
7415:)
7411:1
7408:+
7405:t
7402:2
7399:(
7394:2
7390:t
7386:(
7383:O
7359:2
7355:t
7350:)
7346:1
7343:+
7340:t
7337:2
7334:(
7312:2
7308:t
7281:j
7276:b
7249:i
7244:b
7220:)
7215:2
7212:t
7207:(
7184:t
7181:2
7161:]
7158:1
7152:t
7149:2
7146::
7143:0
7140:[
7120:t
7117:2
7097:0
7077:t
7074:2
7054:c
7034:]
7031:j
7028::
7025:i
7022:[
7019:A
6999:]
6996:j
6993::
6990:i
6987:[
6984:A
6964:S
6944:c
6924:]
6921:j
6918::
6915:i
6912:[
6909:A
6889:j
6863:j
6858:b
6837:i
6811:i
6806:b
6785:)
6782:j
6779:,
6776:i
6773:,
6770:A
6767:(
6764:e
6761:d
6758:o
6755:m
6733:)
6728:2
6724:s
6720:(
6717:O
6695:j
6691:b
6684:.
6681:.
6678:.
6670:1
6667:+
6664:i
6660:b
6651:i
6647:b
6626:]
6623:j
6620:,
6617:i
6614:[
6611:S
6591:s
6585:s
6565:S
6542:s
6538:/
6534:n
6528:=
6525:t
6503:s
6499:b
6495:,
6492:.
6489:.
6486:.
6483:,
6478:2
6474:b
6470:,
6465:1
6461:b
6440:s
6420:A
6396:]
6393:n
6390::
6387:1
6384:[
6381:A
6353:n
6350:=
6347:s
6327:)
6322:2
6318:n
6314:(
6311:O
6290:)
6283:n
6269:n
6250:2
6246:n
6239:(
6235:O
6207:)
6204:s
6200:/
6196:n
6193:(
6190:O
6187:=
6184:)
6181:t
6178:(
6175:O
6155:t
6135:t
6121:.
6107:x
6103:f
6094:c
6090:f
6069:]
6066:x
6063:[
6060:B
6054:c
6032:]
6029:x
6026:[
6023:B
6019:Q
5998:1
5990:c
5986:f
5982:+
5979:]
5976:x
5973:[
5966:B
5945:]
5942:j
5939::
5936:i
5933:[
5930:B
5910:]
5907:x
5904:[
5901:B
5879:x
5875:f
5848:]
5845:j
5842::
5839:x
5836:[
5833:B
5811:c
5807:f
5786:]
5783:j
5780::
5777:i
5774:[
5771:B
5751:]
5748:x
5745:[
5742:B
5719:]
5716:1
5710:x
5707::
5704:i
5701:[
5698:B
5678:i
5672:]
5669:1
5663:]
5660:x
5657:[
5650:B
5646:[
5641:]
5638:x
5635:[
5632:B
5628:Q
5603:x
5570:c
5566:f
5545:]
5542:j
5539::
5536:i
5533:[
5530:B
5510:c
5488:c
5484:f
5463:c
5443:c
5423:]
5420:j
5417::
5414:i
5411:[
5408:B
5388:0
5385:=
5380:c
5376:f
5355:]
5350:j
5346:b
5342:,
5337:i
5333:b
5329:[
5322:S
5299:c
5295:f
5274:]
5269:j
5265:b
5261:,
5256:i
5252:b
5248:[
5245:S
5225:c
5200:i
5196:b
5187:j
5183:b
5162:]
5159:j
5156::
5153:}
5150:i
5147:,
5144:1
5141:+
5138:t
5135:)
5132:1
5129:+
5124:j
5120:b
5116:(
5113:{
5110:x
5107:a
5104:m
5101:[
5098:B
5078:]
5075:}
5072:j
5069:,
5066:t
5061:i
5057:b
5053:{
5050:n
5047:i
5044:m
5041::
5038:i
5035:[
5032:B
5012:B
4992:1
4983:t
4979:/
4975:j
4969:=
4964:j
4960:b
4936:t
4932:/
4928:)
4925:1
4919:i
4916:(
4910:=
4905:i
4901:b
4880:)
4877:j
4874:,
4871:i
4868:,
4865:B
4862:(
4859:e
4856:d
4853:o
4850:m
4827:B
4807:A
4787:A
4767:B
4747:]
4744:j
4741::
4738:i
4735:[
4732:A
4712:]
4709:a
4706:[
4703:A
4683:]
4680:j
4677::
4674:i
4671:[
4668:B
4648:]
4645:a
4642:[
4639:B
4619:j
4616:,
4613:i
4610:,
4607:a
4587:A
4567:B
4472:c
4468:j
4433:S
4425:S
4418:s
4414:D
4410:B
4379:S
4375:,
4372:S
4352:s
4333:B
4313:)
4310:n
4304:s
4301:(
4298:O
4278:)
4273:2
4269:s
4265:(
4262:O
4238:S
4217:]
4214:t
4211:)
4208:1
4205:+
4200:j
4196:b
4192:(
4189::
4186:1
4183:+
4180:t
4175:i
4171:b
4167:[
4164:B
4142:j
4138:b
4131:.
4128:.
4125:.
4117:1
4114:+
4111:i
4107:b
4098:i
4094:b
4073:]
4068:j
4064:b
4060:,
4055:i
4051:b
4047:[
4044:S
4020:S
3999:S
3979:]
3976:t
3973:)
3970:1
3967:+
3964:i
3961:(
3958::
3955:1
3952:+
3949:t
3943:i
3940:[
3937:B
3915:i
3911:b
3887:s
3883:/
3879:n
3873:=
3870:t
3848:s
3844:b
3840:,
3837:.
3834:.
3831:.
3828:,
3823:2
3819:b
3815:,
3810:1
3806:b
3785:s
3762:j
3756:]
3753:1
3747:q
3744:+
3741:]
3738:i
3735:[
3728:B
3724:[
3719:]
3716:i
3713:[
3710:B
3706:Q
3685:q
3665:]
3662:j
3659::
3656:i
3653:[
3650:B
3630:]
3627:i
3624:[
3621:B
3594:B
3567:Q
3563:,
3560:.
3557:.
3554:.
3551:,
3546:2
3542:Q
3538:,
3533:1
3529:Q
3508:B
3486:]
3483:b
3480:[
3477:B
3473:Q
3452:b
3432:]
3429:b
3426:[
3419:B
3398:}
3395:n
3392:,
3389:.
3386:.
3383:.
3380:,
3377:1
3374:{
3368:b
3348:]
3345:n
3342::
3339:1
3336:[
3329:B
3308:}
3305:a
3302:=
3299:]
3296:b
3293:[
3290:B
3285:|
3280:b
3277:{
3274:=
3269:a
3265:Q
3244:}
3238:,
3235:.
3232:.
3229:.
3226:,
3223:1
3220:{
3214:a
3188:Q
3184:,
3181:.
3178:.
3175:.
3172:,
3167:2
3163:Q
3159:,
3154:1
3150:Q
3126:A
3106:D
3103:,
3100:B
3080:D
3060:]
3057:i
3054:[
3051:A
3031:]
3028:i
3025:[
3022:B
3002:i
2982:]
2979:n
2976::
2973:1
2970:[
2967:B
2927:]
2921::
2918:1
2915:[
2912:D
2892:]
2889:n
2886::
2883:1
2880:[
2877:A
2849:)
2844:n
2839:(
2836:O
2816:)
2813:n
2810:(
2807:O
2785:n
2780:=
2777:s
2757:)
2754:s
2750:/
2746:n
2743:(
2740:O
2720:)
2715:2
2711:s
2707:+
2704:n
2701:(
2698:O
2670:b
2650:a
2630:)
2627:]
2624:k
2621::
2618:i
2615:[
2612:A
2609:(
2606:e
2603:d
2600:o
2597:m
2577:c
2557:b
2537:a
2517:]
2514:k
2511::
2508:i
2505:[
2502:A
2482:b
2476:c
2470:a
2450:]
2447:k
2444::
2441:1
2438:+
2435:j
2432:[
2429:A
2409:1
2401:a
2397:f
2376:]
2373:j
2370::
2367:i
2364:[
2361:A
2341:1
2333:a
2329:f
2308:c
2286:a
2282:f
2261:b
2258:=
2255:)
2252:]
2249:k
2246::
2243:1
2240:+
2237:j
2234:[
2231:A
2228:(
2225:e
2222:d
2219:o
2216:m
2194:a
2190:f
2169:a
2166:=
2163:)
2160:]
2157:j
2154::
2151:i
2148:[
2145:A
2142:(
2139:e
2136:d
2133:o
2130:m
2110:]
2107:k
2104::
2101:1
2098:+
2095:j
2092:[
2089:A
2069:]
2066:j
2063::
2060:i
2057:[
2054:A
2034:]
2031:k
2028::
2025:i
2022:[
2019:A
1999:]
1996:k
1993::
1990:1
1987:+
1984:j
1981:[
1978:A
1958:]
1955:j
1952::
1949:i
1946:[
1943:A
1918:)
1912:)
1909:n
1905:/
1901:w
1898:S
1895:(
1884:n
1872:(
1848:w
1828:S
1796:2
1792:/
1788:1
1776:0
1755:)
1752:n
1737:n
1733:(
1730:O
1709:)
1701:2
1695:2
1691:n
1687:(
1684:O
1659:2
1655:/
1651:1
1639:0
1618:)
1609:n
1605:(
1602:O
1581:)
1578:n
1568:/
1559:2
1553:2
1549:n
1545:(
1542:O
1515:)
1512:1
1509:(
1506:O
1485:)
1482:n
1472:/
1468:n
1451:2
1447:n
1443:(
1440:O
1414:w
1393:)
1388:w
1384:/
1380:n
1375:(
1372:O
1351:)
1348:n
1345:(
1342:O
1315:)
1310:n
1305:(
1302:O
1281:)
1278:n
1275:(
1272:O
1228:C
1208:b
1186:c
1182:f
1173:b
1169:f
1148:A
1142:c
1122:B
1102:b
1082:B
1060:b
1056:f
1035:b
1015:B
995:c
975:C
953:c
949:f
928:B
922:A
919:=
916:C
896:A
890:c
862:B
842:c
822:A
816:c
796:B
790:A
770:c
746:B
726:A
698:]
693:j
689:a
685:,
682:.
679:.
676:.
673:,
668:1
665:+
662:i
658:a
654:,
649:i
645:a
641:[
638:=
635:]
632:j
629::
626:i
623:[
620:A
600:2
597:=
594:)
591:S
588:(
585:e
582:d
579:o
576:m
556:]
553:2
550:,
547:4
544:,
541:3
538:,
535:2
532:,
529:4
526:,
523:2
520:,
517:1
514:[
511:=
508:S
488:}
485:k
482:,
479:.
476:.
473:.
470:,
467:1
464:{
458:j
449:j
445:s
422:i
418:s
395:i
391:s
370:]
365:k
361:s
357:,
354:.
351:.
348:.
345:,
340:2
336:s
332:,
327:1
323:s
319:[
316:=
313:S
293:)
290:S
287:(
284:e
281:d
278:o
275:m
255:n
249:j
243:i
237:1
217:)
214:j
211::
208:i
205:,
202:A
199:(
196:e
193:d
190:o
187:m
167:]
162:n
158:a
154:,
151:.
148:.
145:.
142:,
137:2
133:a
129:,
124:1
120:a
116:[
113:=
110:]
107:n
104::
101:1
98:[
95:A
62:)
56:(
51:)
47:(
33:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.