<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">

Last update:

This is handled in the <code>sum(int l, int r)</code> method.</p>

<p>Also this implementation supports two constructors.

You can create a Fenwick tree initialized with zeros, or you can convert an existing array into the Fenwick form.</p>

<div class="tabbed-content">

<div class="highlight"><pre><span></span><code><span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="nc">FenwickTree</span><span class="w"> </span><span class="p">{</span>

<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>

<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">n</span><span class="p">;</span>

<span class="w"> </span><span class="p">}</span>

<span class="w"> </span><span class="p">};</span>

<div class="tabbed-block">

<div class="highlight"><pre><span></span><code><span class="k">class</span><span class="w"> </span><span class="nc">FenwickTree</span><span class="p">:</span>

<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>.

Additionally, each time a value is <code>update</code>'d, the new value has to be smaller than the current value.

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>

<div class="tabbed-content">

<div class="highlight"><pre><span></span><code><span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="nc">FenwickTreeMin</span><span class="w"> </span><span class="p">{</span>

<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="kt">int</span><span class="w"> </span><span class="n">n</span><span class="p">;</span>

<span class="w"> </span><span class="p">}</span>

<span class="w"> </span><span class="p">};</span>

<div class="tabbed-block">

<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>

The implementation is also a lot harder compared to the normal implementation for sums.</p>

<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>

<p>As claimed before, it is very easy to implement Fenwick Tree for multidimensional array.</p>

<div class="tabbed-content">

<div class="tabbed-block">

<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>

<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.

We want <span class="arithmatex">$T[i]$</span> to store the sum of <span class="arithmatex">$[g(i)+1; i]$</span>.

This changes the implementation a little bit, and allows for a similar nice definition for <span class="arithmatex">$g(i)$</span>:</p>

<div class="tabbed-content">

<div class="tabbed-block">

<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>

<div class="arithmatex">$$h(i) = i + (i ~\&amp;~ (-i)).$$</div>

<p>As you can see, the main benefit of this approach is that the binary operations complement each other very nicely.</p>

<p>The following implementation can be used like the other implementations, however it uses one-based indexing internally.</p>

<div class="tabbed-content">

<div class="tabbed-block">

<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>

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.

And if <span class="arithmatex">$i &gt; r$</span>, then the second update operation will cancel the effect of first one.</p>

<p>The following implementation uses one-based indexing.</p>

<div class="tabbed-content">

<div class="tabbed-block">

<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>

<p>Suppose that we want to increment the interval <span class="arithmatex">$[l, r]$</span> by the value <span class="arithmatex">$x$</span>.

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>.

And we also update <span class="arithmatex">$B_2$</span>. The details will be explained later.</p>

<div class="tabbed-content">

<div class="tabbed-block">

<p>```cpp

<p>The last expression is exactly equal to the required terms.

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>

<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>

<div class="tabbed-content">

<div class="tabbed-block">

<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>