Skip to content

Commit a392ed3

Browse files
1 parent 64806f7 commit a392ed3

File tree

5 files changed

+7
-23
lines changed

5 files changed

+7
-23
lines changed

main/data_structures/sqrt_decomposition.html

Lines changed: 3 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -6559,18 +6559,6 @@
65596559

65606560

65616561

6562-
6563-
6564-
6565-
6566-
6567-
6568-
6569-
6570-
6571-
6572-
6573-
65746562

65756563

65766564

@@ -6741,10 +6729,6 @@
67416729

67426730

67436731

6744-
6745-
6746-
6747-
67486732

67496733

67506734

@@ -6757,7 +6741,7 @@
67576741
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
67586742

67596743
Last update:
6760-
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">December 20, 2024</span>&emsp;
6744+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">October 1, 2024</span>&emsp;
67616745

67626746
<!-- Tags -->
67636747

@@ -6864,7 +6848,7 @@ <h2 id="mos-algorithm">Mo's algorithm<a class="headerlink" href="#mos-algorithm"
68646848
During a normal sqrt decomposition, we have to precompute the answers for each block, and merge them during answering queries.
68656849
In some problems this merging step can be quite problematic.
68666850
E.g. when each queries asks to find the <strong>mode</strong> of its range (the number that appears the most often).
6867-
For this each block would have to store the count of each number in it in some sort of data structure, and we can no longer perform the merge step fast enough any more.
6851+
For this each block would have to store the count of each number in it in some sort of data structure, and we cannot longer perform the merge step fast enough any more.
68686852
<strong>Mo's algorithm</strong> uses a completely different approach, that can answer these kind of queries fast, because it only keeps track of one data structure, and the only operations with it are easy and fast.</p>
68696853
<p>The idea is to answer the queries in a special order based on the indices.
68706854
We will first answer all queries which have the left index in block 0, then answer all queries which have left index in block 1 and so on.
@@ -6974,7 +6958,7 @@ <h2 id="practice-problems">Practice Problems<a class="headerlink" href="#practic
69746958

69756959
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
69766960
<span class="contributors-text">Contributors:</span>
6977-
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/madhur4127" title="madhur4127" data-bi-name="contributorprofile" target="_blank">madhur4127</a> (56.22%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (25.3%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (4.02%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (3.61%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (3.21%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (2.01%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (1.2%)</li><li><a href="https://github.com/gampu" title="gampu" data-bi-name="contributorprofile" target="_blank">gampu</a> (1.2%)</li><li><a href="https://github.com/ypratik817" title="ypratik817" data-bi-name="contributorprofile" target="_blank">ypratik817</a> (0.4%)</li><li><a href="https://github.com/abirc8010" title="abirc8010" data-bi-name="contributorprofile" target="_blank">abirc8010</a> (0.4%)</li><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (0.4%)</li><li><a href="https://github.com/3centroids" title="3centroids" data-bi-name="contributorprofile" target="_blank">3centroids</a> (0.4%)</li><li><a href="https://github.com/mrpandey" title="mrpandey" data-bi-name="contributorprofile" target="_blank">mrpandey</a> (0.4%)</li><li><a href="https://github.com/rajatdiptabiswas" title="rajatdiptabiswas" data-bi-name="contributorprofile" target="_blank">rajatdiptabiswas</a> (0.4%)</li><li><a href="https://github.com/meooow25" title="meooow25" data-bi-name="contributorprofile" target="_blank">meooow25</a> (0.4%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.4%)</li></ul>
6961+
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/madhur4127" title="madhur4127" data-bi-name="contributorprofile" target="_blank">madhur4127</a> (56.63%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (25.3%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (4.02%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (3.61%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (3.21%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (2.01%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (1.2%)</li><li><a href="https://github.com/gampu" title="gampu" data-bi-name="contributorprofile" target="_blank">gampu</a> (1.2%)</li><li><a href="https://github.com/abirc8010" title="abirc8010" data-bi-name="contributorprofile" target="_blank">abirc8010</a> (0.4%)</li><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (0.4%)</li><li><a href="https://github.com/3centroids" title="3centroids" data-bi-name="contributorprofile" target="_blank">3centroids</a> (0.4%)</li><li><a href="https://github.com/mrpandey" title="mrpandey" data-bi-name="contributorprofile" target="_blank">mrpandey</a> (0.4%)</li><li><a href="https://github.com/rajatdiptabiswas" title="rajatdiptabiswas" data-bi-name="contributorprofile" target="_blank">rajatdiptabiswas</a> (0.4%)</li><li><a href="https://github.com/meooow25" title="meooow25" data-bi-name="contributorprofile" target="_blank">meooow25</a> (0.4%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.4%)</li></ul>
69786962
</ul>
69796963

69806964
</article>

0 commit comments

Comments
 (0)