Skip to content

Commit 095a24d

Browse files
1 parent a71482e commit 095a24d

File tree

9 files changed

+223
-179
lines changed

9 files changed

+223
-179
lines changed

1563/data_structures/fenwick.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8328,7 +8328,7 @@
83288328
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
83298329

83308330
Last update:
8331-
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="November 22, 2025 08:40:38 UTC">November 22, 2025</span>&emsp;
8331+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="November 26, 2025 02:34:03 UTC">November 26, 2025</span>&emsp;
83328332

83338333
<!-- Tags -->
83348334

1563/data_structures/segment_tree.html

Lines changed: 21 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8273,6 +8273,20 @@
82738273

82748274

82758275

8276+
8277+
8278+
8279+
8280+
8281+
8282+
8283+
8284+
8285+
8286+
8287+
8288+
8289+
82768290

82778291

82788292

@@ -8641,6 +8655,10 @@
86418655

86428656

86438657

8658+
8659+
8660+
8661+
86448662

86458663

86468664

@@ -8653,7 +8671,7 @@
86538671
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
86548672

86558673
Last update:
8656-
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="December 20, 2023 20:45:55 UTC">December 20, 2023</span>&emsp;
8674+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="November 23, 2025 02:03:42 UTC">November 23, 2025</span>&emsp;
86578675

86588676
<!-- Tags -->
86598677

@@ -9186,7 +9204,7 @@ <h4 id="find-the-smallest-number-greater-or-equal-to-a-specified-number-accelera
91869204
<p>But notice, that this uses three times more memory than a normal Merge Sort Tree, which already uses a lot of memory (<span class="arithmatex">$O(n \log n)$</span>).</p>
91879205
<p>It is straightforward to apply this technique to a problem, that doesn't require any modification queries.
91889206
The two positions are just integers and can easily be computed by counting when merging the two sorted sequences.</p>
9189-
<p>It it still possible to also allow modification queries, but that complicates the entire code.
9207+
<p>It is still possible to also allow modification queries, but that complicates the entire code.
91909208
Instead of integers, you need to store the sorted array as <code>multiset</code>, and instead of indices you need to store iterators.
91919209
And you need to work very carefully, so that you increment or decrement the correct iterators during a modification query.</p>
91929210
<h4 id="other-possible-variations">Other possible variations<a class="headerlink" href="#other-possible-variations" title="Permanent link">&para;</a></h4>
@@ -9655,7 +9673,7 @@ <h2 id="practice-problems">Practice Problems<a class="headerlink" href="#practic
96559673

96569674
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
96579675
<span class="contributors-text">Contributors:</span>
9658-
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (76.98%)</li><li><a href="https://github.com/dasfex" title="dasfex" data-bi-name="contributorprofile" target="_blank">dasfex</a> (5.45%)</li><li><a href="https://github.com/arjan-bal" title="arjan-bal" data-bi-name="contributorprofile" target="_blank">arjan-bal</a> (4.54%)</li><li><a href="https://github.com/tpoppo" title="tpoppo" data-bi-name="contributorprofile" target="_blank">tpoppo</a> (1.82%)</li><li><a href="https://github.com/GaurangTandon" title="GaurangTandon" data-bi-name="contributorprofile" target="_blank">GaurangTandon</a> (1.65%)</li><li><a href="https://github.com/masterchef2209" title="masterchef2209" data-bi-name="contributorprofile" target="_blank">masterchef2209</a> (1.32%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (1.24%)</li><li><a href="https://github.com/akoutian" title="akoutian" data-bi-name="contributorprofile" target="_blank">akoutian</a> (0.91%)</li><li><a href="https://github.com/L1nkus" title="L1nkus" data-bi-name="contributorprofile" target="_blank">L1nkus</a> (0.91%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (0.82%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (0.58%)</li><li><a href="https://github.com/kerolloz" title="kerolloz" data-bi-name="contributorprofile" target="_blank">kerolloz</a> (0.58%)</li><li><a href="https://github.com/pr4shan7" title="pr4shan7" data-bi-name="contributorprofile" target="_blank">pr4shan7</a> (0.5%)</li><li><a href="https://github.com/mhayter" title="mhayter" data-bi-name="contributorprofile" target="_blank">mhayter</a> (0.41%)</li><li><a href="https://github.com/huggin" title="huggin" data-bi-name="contributorprofile" target="_blank">huggin</a> (0.33%)</li><li><a href="https://github.com/zyrch" title="zyrch" data-bi-name="contributorprofile" target="_blank">zyrch</a> (0.25%)</li><li><a href="https://github.com/SiddharthEEE" title="SiddharthEEE" data-bi-name="contributorprofile" target="_blank">SiddharthEEE</a> (0.17%)</li><li><a href="https://github.com/xirc" title="xirc" data-bi-name="contributorprofile" target="_blank">xirc</a> (0.17%)</li><li><a href="https://github.com/boxlesscat" title="boxlesscat" data-bi-name="contributorprofile" target="_blank">boxlesscat</a> (0.08%)</li><li><a href="https://github.com/3centroids" title="3centroids" data-bi-name="contributorprofile" target="_blank">3centroids</a> (0.08%)</li><li><a href="https://github.com/mehrdad3301" title="mehrdad3301" data-bi-name="contributorprofile" target="_blank">mehrdad3301</a> (0.08%)</li><li><a href="https://github.com/scion03" title="scion03" data-bi-name="contributorprofile" target="_blank">scion03</a> (0.08%)</li><li><a href="https://github.com/DevChoganwala" title="DevChoganwala" data-bi-name="contributorprofile" target="_blank">DevChoganwala</a> (0.08%)</li><li><a href="https://github.com/Abhishek-Saini" title="Abhishek-Saini" data-bi-name="contributorprofile" target="_blank">Abhishek-Saini</a> (0.08%)</li><li><a href="https://github.com/tarptaeya" title="tarptaeya" data-bi-name="contributorprofile" target="_blank">tarptaeya</a> (0.08%)</li><li><a href="https://github.com/it-is-skywalkerl" title="it-is-skywalkerl" data-bi-name="contributorprofile" target="_blank">it-is-skywalkerl</a> (0.08%)</li><li><a href="https://github.com/forsythe" title="forsythe" data-bi-name="contributorprofile" target="_blank">forsythe</a> (0.08%)</li><li><a href="https://github.com/ChangMarkusYu" title="ChangMarkusYu" data-bi-name="contributorprofile" target="_blank">ChangMarkusYu</a> (0.08%)</li><li><a href="https://github.com/aryamanjain-scifin" title="aryamanjain-scifin" data-bi-name="contributorprofile" target="_blank">aryamanjain-scifin</a> (0.08%)</li><li><a href="https://github.com/ArthurConmy" title="ArthurConmy" data-bi-name="contributorprofile" target="_blank">ArthurConmy</a> (0.08%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (0.08%)</li><li><a href="https://github.com/idleft" title="idleft" data-bi-name="contributorprofile" target="_blank">idleft</a> (0.08%)</li><li><a href="https://github.com/Naman-Bhalla" title="Naman-Bhalla" data-bi-name="contributorprofile" target="_blank">Naman-Bhalla</a> (0.08%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (0.08%)</li><li><a href="https://github.com/prashantkn94" title="prashantkn94" data-bi-name="contributorprofile" target="_blank">prashantkn94</a> (0.08%)</li></ul>
9676+
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (76.9%)</li><li><a href="https://github.com/dasfex" title="dasfex" data-bi-name="contributorprofile" target="_blank">dasfex</a> (5.45%)</li><li><a href="https://github.com/arjan-bal" title="arjan-bal" data-bi-name="contributorprofile" target="_blank">arjan-bal</a> (4.54%)</li><li><a href="https://github.com/tpoppo" title="tpoppo" data-bi-name="contributorprofile" target="_blank">tpoppo</a> (1.82%)</li><li><a href="https://github.com/GaurangTandon" title="GaurangTandon" data-bi-name="contributorprofile" target="_blank">GaurangTandon</a> (1.65%)</li><li><a href="https://github.com/masterchef2209" title="masterchef2209" data-bi-name="contributorprofile" target="_blank">masterchef2209</a> (1.32%)</li><li><a href="https://github.com/jxu" title="jxu" data-bi-name="contributorprofile" target="_blank">jxu</a> (1.24%)</li><li><a href="https://github.com/akoutian" title="akoutian" data-bi-name="contributorprofile" target="_blank">akoutian</a> (0.91%)</li><li><a href="https://github.com/L1nkus" title="L1nkus" data-bi-name="contributorprofile" target="_blank">L1nkus</a> (0.91%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (0.82%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (0.58%)</li><li><a href="https://github.com/kerolloz" title="kerolloz" data-bi-name="contributorprofile" target="_blank">kerolloz</a> (0.58%)</li><li><a href="https://github.com/pr4shan7" title="pr4shan7" data-bi-name="contributorprofile" target="_blank">pr4shan7</a> (0.5%)</li><li><a href="https://github.com/mhayter" title="mhayter" data-bi-name="contributorprofile" target="_blank">mhayter</a> (0.41%)</li><li><a href="https://github.com/huggin" title="huggin" data-bi-name="contributorprofile" target="_blank">huggin</a> (0.33%)</li><li><a href="https://github.com/zyrch" title="zyrch" data-bi-name="contributorprofile" target="_blank">zyrch</a> (0.25%)</li><li><a href="https://github.com/SiddharthEEE" title="SiddharthEEE" data-bi-name="contributorprofile" target="_blank">SiddharthEEE</a> (0.17%)</li><li><a href="https://github.com/xirc" title="xirc" data-bi-name="contributorprofile" target="_blank">xirc</a> (0.17%)</li><li><a href="https://github.com/het-t" title="het-t" data-bi-name="contributorprofile" target="_blank">het-t</a> (0.08%)</li><li><a href="https://github.com/boxlesscat" title="boxlesscat" data-bi-name="contributorprofile" target="_blank">boxlesscat</a> (0.08%)</li><li><a href="https://github.com/3centroids" title="3centroids" data-bi-name="contributorprofile" target="_blank">3centroids</a> (0.08%)</li><li><a href="https://github.com/mehrdad3301" title="mehrdad3301" data-bi-name="contributorprofile" target="_blank">mehrdad3301</a> (0.08%)</li><li><a href="https://github.com/scion03" title="scion03" data-bi-name="contributorprofile" target="_blank">scion03</a> (0.08%)</li><li><a href="https://github.com/DevChoganwala" title="DevChoganwala" data-bi-name="contributorprofile" target="_blank">DevChoganwala</a> (0.08%)</li><li><a href="https://github.com/Abhishek-Saini" title="Abhishek-Saini" data-bi-name="contributorprofile" target="_blank">Abhishek-Saini</a> (0.08%)</li><li><a href="https://github.com/tarptaeya" title="tarptaeya" data-bi-name="contributorprofile" target="_blank">tarptaeya</a> (0.08%)</li><li><a href="https://github.com/it-is-skywalkerl" title="it-is-skywalkerl" data-bi-name="contributorprofile" target="_blank">it-is-skywalkerl</a> (0.08%)</li><li><a href="https://github.com/forsythe" title="forsythe" data-bi-name="contributorprofile" target="_blank">forsythe</a> (0.08%)</li><li><a href="https://github.com/ChangMarkusYu" title="ChangMarkusYu" data-bi-name="contributorprofile" target="_blank">ChangMarkusYu</a> (0.08%)</li><li><a href="https://github.com/aryamanjain-scifin" title="aryamanjain-scifin" data-bi-name="contributorprofile" target="_blank">aryamanjain-scifin</a> (0.08%)</li><li><a href="https://github.com/ArthurConmy" title="ArthurConmy" data-bi-name="contributorprofile" target="_blank">ArthurConmy</a> (0.08%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (0.08%)</li><li><a href="https://github.com/idleft" title="idleft" data-bi-name="contributorprofile" target="_blank">idleft</a> (0.08%)</li><li><a href="https://github.com/Naman-Bhalla" title="Naman-Bhalla" data-bi-name="contributorprofile" target="_blank">Naman-Bhalla</a> (0.08%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (0.08%)</li><li><a href="https://github.com/prashantkn94" title="prashantkn94" data-bi-name="contributorprofile" target="_blank">prashantkn94</a> (0.08%)</li></ul>
96599677
</ul>
96609678

96619679
</article>

0 commit comments

Comments
 (0)