Skip to content

Commit 96bc6ad

Browse files
github-actions[bot]github-actions[bot]
committed
1 parent bb665dc commit 96bc6ad

File tree

5 files changed

+22
-16
lines changed

5 files changed

+22
-16
lines changed

‎1563/data_structures/fenwick.html‎

Lines changed: 18 additions & 12 deletions
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="December 6, 2025 06:25:10 UTC">December 6, 2025</span>&emsp;
8331+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="December 6, 2025 06:29:22 UTC">December 6, 2025</span>&emsp;
83328332

83338333
<!-- Tags -->
83348334

@@ -8570,9 +8570,11 @@ <h3 id="finding-minimum-of-0-r-in-one-dimensional-array">Finding minimum of <spa
85708570
<p>It is obvious that there is no easy way of finding minimum of range <span class="arithmatex">$[l, r]$</span> using Fenwick tree, as Fenwick tree can only answer queries of type <span class="arithmatex">$[0, r]$</span>.
85718571
Additionally, each time a value is <code>update</code>'d, the new value has to be smaller than the current value.
85728572
Both significant limitations are because the <span class="arithmatex">$min$</span> operation together with the set of integers doesn't form a group, as there are no inverse elements.</p>
8573-
<div class="tabbed-set tabbed-alternate" data-tabs="4:2"><input checked="checked" id="__tabbed_4_1" name="__tabbed_4" type="radio" /><input id="__tabbed_4_2" name="__tabbed_4" type="radio" /><div class="tabbed-labels"><label for="__tabbed_4_1">C++</label><label for="__tabbed_4_2">Python</label></div>
8573+
<div class="tabbed-set tabbed-alternate" data-tabs="4:1"><input checked="checked" id="__tabbed_4_1" name="__tabbed_4" type="radio" /><div class="tabbed-labels"><label for="__tabbed_4_1">C++</label></div>
85748574
<div class="tabbed-content">
8575-
<div class="tabbed-block">
8575+
<div class="tabbed-block"></div>
8576+
</div>
8577+
</div>
85768578
<div class="highlight"><pre><span></span><code><span class="k">struct</span><span class="w"> </span><span class="nc">FenwickTreeMin</span><span class="w"> </span><span class="p">{</span>
85778579
<span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">bit</span><span class="p">;</span>
85788580
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="p">;</span>
@@ -8601,7 +8603,8 @@ <h3 id="finding-minimum-of-0-r-in-one-dimensional-array">Finding minimum of <spa
86018603
<span class="w"> </span><span class="p">}</span>
86028604
<span class="p">};</span>
86038605
</code></pre></div>
8604-
</div>
8606+
<div class="tabbed-set tabbed-alternate" data-tabs="5:1"><input checked="checked" id="__tabbed_5_1" name="__tabbed_5" type="radio" /><div class="tabbed-labels"><label for="__tabbed_5_1">Python</label></div>
8607+
<div class="tabbed-content">
86058608
<div class="tabbed-block">
86068609
<div class="highlight"><pre><span></span><code><span class="k">class</span><span class="w"> </span><span class="nc">FenwickTreeMin</span><span class="p">:</span>
86078610

@@ -8640,7 +8643,7 @@ <h3 id="finding-minimum-of-0-r-in-one-dimensional-array">Finding minimum of <spa
86408643
The implementation is also a lot harder compared to the normal implementation for sums.</p>
86418644
<h3 id="finding-sum-in-two-dimensional-array">Finding sum in two-dimensional array<a class="headerlink" href="#finding-sum-in-two-dimensional-array" title="Permanent link">&para;</a></h3>
86428645
<p>As claimed before, it is very easy to implement Fenwick Tree for multidimensional array.</p>
8643-
<div class="tabbed-set tabbed-alternate" data-tabs="5:2"><input checked="checked" id="__tabbed_5_1" name="__tabbed_5" type="radio" /><input id="__tabbed_5_2" name="__tabbed_5" type="radio" /><div class="tabbed-labels"><label for="__tabbed_5_1">C++</label><label for="__tabbed_5_2">Python</label></div>
8646+
<div class="tabbed-set tabbed-alternate" data-tabs="6:2"><input checked="checked" id="__tabbed_6_1" name="__tabbed_6" type="radio" /><input id="__tabbed_6_2" name="__tabbed_6" type="radio" /><div class="tabbed-labels"><label for="__tabbed_6_1">C++</label><label for="__tabbed_6_2">Python</label></div>
86448647
<div class="tabbed-content">
86458648
<div class="tabbed-block">
86468649
<div class="highlight"><pre><span></span><code><span class="k">struct</span><span class="w"> </span><span class="nc">FenwickTree2D</span><span class="w"> </span><span class="p">{</span>
@@ -8700,7 +8703,7 @@ <h3 id="one-based-indexing-approach">One-based indexing approach<a class="header
87008703
<p>For this approach we change the requirements and definition for <span class="arithmatex">$T[]$</span> and <span class="arithmatex">$g()$</span> a little bit.
87018704
We want <span class="arithmatex">$T[i]$</span> to store the sum of <span class="arithmatex">$[g(i)+1; i]$</span>.
87028705
This changes the implementation a little bit, and allows for a similar nice definition for <span class="arithmatex">$g(i)$</span>:</p>
8703-
<div class="tabbed-set tabbed-alternate" data-tabs="6:2"><input checked="checked" id="__tabbed_6_1" name="__tabbed_6" type="radio" /><input id="__tabbed_6_2" name="__tabbed_6" type="radio" /><div class="tabbed-labels"><label for="__tabbed_6_1">C++</label><label for="__tabbed_6_2">Python</label></div>
8706+
<div class="tabbed-set tabbed-alternate" data-tabs="7:2"><input checked="checked" id="__tabbed_7_1" name="__tabbed_7" type="radio" /><input id="__tabbed_7_2" name="__tabbed_7" type="radio" /><div class="tabbed-labels"><label for="__tabbed_7_1">C++</label><label for="__tabbed_7_2">Python</label></div>
87048707
<div class="tabbed-content">
87058708
<div class="tabbed-block">
87068709
<div class="highlight"><pre><span></span><code><span class="kt">int</span><span class="w"> </span><span class="nf">sum</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
@@ -8749,9 +8752,11 @@ <h3 id="one-based-indexing-approach">One-based indexing approach<a class="header
87498752
<div class="arithmatex">$$h(i) = i + (i ~\&amp;~ (-i)).$$</div>
87508753
<p>As you can see, the main benefit of this approach is that the binary operations complement each other very nicely.</p>
87518754
<p>The following implementation can be used like the other implementations, however it uses one-based indexing internally.</p>
8752-
<div class="tabbed-set tabbed-alternate" data-tabs="7:2"><input checked="checked" id="__tabbed_7_1" name="__tabbed_7" type="radio" /><input id="__tabbed_7_2" name="__tabbed_7" type="radio" /><div class="tabbed-labels"><label for="__tabbed_7_1">C++</label><label for="__tabbed_7_2">Python</label></div>
8755+
<div class="tabbed-set tabbed-alternate" data-tabs="8:1"><input checked="checked" id="__tabbed_8_1" name="__tabbed_8" type="radio" /><div class="tabbed-labels"><label for="__tabbed_8_1">C++</label></div>
87538756
<div class="tabbed-content">
8754-
<div class="tabbed-block">
8757+
<div class="tabbed-block"></div>
8758+
</div>
8759+
</div>
87558760
<div class="highlight"><pre><span></span><code><span class="k">struct</span><span class="w"> </span><span class="nc">FenwickTreeOneBasedIndexing</span><span class="w"> </span><span class="p">{</span>
87568761
<span class="w"> </span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">bit</span><span class="p">;</span><span class="w"> </span><span class="c1">// binary indexed tree</span>
87578762
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="p">;</span>
@@ -8784,7 +8789,8 @@ <h3 id="one-based-indexing-approach">One-based indexing approach<a class="header
87848789
<span class="w"> </span><span class="p">}</span>
87858790
<span class="p">};</span>
87868791
</code></pre></div>
8787-
</div>
8792+
<div class="tabbed-set tabbed-alternate" data-tabs="9:1"><input checked="checked" id="__tabbed_9_1" name="__tabbed_9" type="radio" /><div class="tabbed-labels"><label for="__tabbed_9_1">Python</label></div>
8793+
<div class="tabbed-content">
87888794
<div class="tabbed-block">
87898795
<div class="highlight"><pre><span></span><code><span class="k">class</span><span class="w"> </span><span class="nc">FenwickTreeOneBasedIndexing</span><span class="p">:</span>
87908796

@@ -8836,7 +8842,7 @@ <h3 id="2-range-update-and-point-query">2. Range Update and Point Query<a class=
88368842
If <span class="arithmatex">$i \in [l, r]$</span>, then we get the answer <span class="arithmatex">$x$</span> because of the first update operation.
88378843
And if <span class="arithmatex">$i &gt; r$</span>, then the second update operation will cancel the effect of first one.</p>
88388844
<p>The following implementation uses one-based indexing.</p>
8839-
<div class="tabbed-set tabbed-alternate" data-tabs="8:2"><input checked="checked" id="__tabbed_8_1" name="__tabbed_8" type="radio" /><input id="__tabbed_8_2" name="__tabbed_8" type="radio" /><div class="tabbed-labels"><label for="__tabbed_8_1">C++</label><label for="__tabbed_8_2">Python</label></div>
8845+
<div class="tabbed-set tabbed-alternate" data-tabs="10:2"><input checked="checked" id="__tabbed_10_1" name="__tabbed_10" type="radio" /><input id="__tabbed_10_2" name="__tabbed_10" type="radio" /><div class="tabbed-labels"><label for="__tabbed_10_1">C++</label><label for="__tabbed_10_2">Python</label></div>
88408846
<div class="tabbed-content">
88418847
<div class="tabbed-block">
88428848
<div class="highlight"><pre><span></span><code><span class="kt">void</span><span class="w"> </span><span class="nf">add</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">idx</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">val</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
@@ -8884,7 +8890,7 @@ <h3 id="3-range-update-and-range-query">3. Range Update and Range Query<a class=
88848890
<p>Suppose that we want to increment the interval <span class="arithmatex">$[l, r]$</span> by the value <span class="arithmatex">$x$</span>.
88858891
Similarly as in the previous method, we perform two point updates on <span class="arithmatex">$B_1$</span>: <code>add(B1, l, x)</code> and <code>add(B1, r+1, -x)</code>.
88868892
And we also update <span class="arithmatex">$B_2$</span>. The details will be explained later.</p>
8887-
<div class="tabbed-set tabbed-alternate" data-tabs="9:2"><input checked="checked" id="__tabbed_9_1" name="__tabbed_9" type="radio" /><input id="__tabbed_9_2" name="__tabbed_9" type="radio" /><div class="tabbed-labels"><label for="__tabbed_9_1">C++</label><label for="__tabbed_9_2">Python</label></div>
8893+
<div class="tabbed-set tabbed-alternate" data-tabs="11:2"><input checked="checked" id="__tabbed_11_1" name="__tabbed_11" type="radio" /><input id="__tabbed_11_2" name="__tabbed_11" type="radio" /><div class="tabbed-labels"><label for="__tabbed_11_1">C++</label><label for="__tabbed_11_2">Python</label></div>
88888894
<div class="tabbed-content">
88898895
<div class="tabbed-block">
88908896
<p>```cpp
@@ -8928,7 +8934,7 @@ <h3 id="3-range-update-and-range-query">3. Range Update and Range Query<a class=
89288934
<p>The last expression is exactly equal to the required terms.
89298935
Thus we can use <span class="arithmatex">$B_2$</span> for shaving off extra terms when we multiply <span class="arithmatex">$B_1[i]\times i$</span>.</p>
89308936
<p>We can find arbitrary range sums by computing the prefix sums for <span class="arithmatex">$l-1$</span> and <span class="arithmatex">$r$</span> and taking the difference of them again.</p>
8931-
<div class="tabbed-set tabbed-alternate" data-tabs="10:2"><input checked="checked" id="__tabbed_10_1" name="__tabbed_10" type="radio" /><input id="__tabbed_10_2" name="__tabbed_10" type="radio" /><div class="tabbed-labels"><label for="__tabbed_10_1">C++</label><label for="__tabbed_10_2">Python</label></div>
8937+
<div class="tabbed-set tabbed-alternate" data-tabs="12:2"><input checked="checked" id="__tabbed_12_1" name="__tabbed_12" type="radio" /><input id="__tabbed_12_2" name="__tabbed_12" type="radio" /><div class="tabbed-labels"><label for="__tabbed_12_1">C++</label><label for="__tabbed_12_2">Python</label></div>
89328938
<div class="tabbed-content">
89338939
<div class="tabbed-block">
89348940
<div class="highlight"><pre><span></span><code><span class="kt">void</span><span class="w"> </span><span class="nf">add</span><span class="p">(</span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="o">&amp;</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">idx</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>

0 commit comments

Comments
 (0)