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

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">November 13, 2024</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">March 24, 2025</span>&emsp;

In order to simplify the code, this function always does two recursive calls, even if only one is necessary - in that case the superfluous recursive call will have<spanclass="arithmatex">$l &gt; r$</span>, and this can easily be caught using an additional check at the beginning of the function.</p>

<divclass="highlight"><pre><span></span><code><spanclass="kt">int</span><spanclass="w"></span><spanclass="nf">sum</span><spanclass="p">(</span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">v</span><spanclass="p">,</span><spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">tl</span><spanclass="p">,</span><spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">tr</span><spanclass="p">,</span><spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">l</span><spanclass="p">,</span><spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">r</span><spanclass="p">)</span><spanclass="w"></span><spanclass="p">{</span>

<spanclass="w"></span><spanclass="k">if</span><spanclass="w"></span><spanclass="p">(</span><spanclass="n">tr</span><spanclass="w"></span><spanclass="o">&lt;</span><spanclass="w"></span><spanclass="n">l</span><spanclass="w"></span><spanclass="o">||</span><spanclass="w"></span><spanclass="n">tl</span><spanclass="w"></span><spanclass="o">&gt;</span><spanclass="w"></span><spanclass="n">r</span><spanclass="p">)</span><spanclass="w"></span><spanclass="k">return</span><spanclass="w"></span><spanclass="mi">0</span><spanclass="p">;</span><spanclass="w"></span><spanclass="c1">// no overlap</span>

<spanclass="w"></span><spanclass="k">if</span><spanclass="w"></span><spanclass="p">(</span><spanclass="n">tl</span><spanclass="w"></span><spanclass="o">&gt;=</span><spanclass="w"></span><spanclass="n">l</span><spanclass="w"></span><spanclass="o">&amp;&amp;</span><spanclass="w"></span><spanclass="n">tr</span><spanclass="w"></span><spanclass="o">&lt;=</span><spanclass="w"></span><spanclass="n">r</span><spanclass="p">)</span><spanclass="w"></span><spanclass="k">return</span><spanclass="w"></span><spanclass="n">t</span><spanclass="p">[</span><spanclass="n">v</span><spanclass="p">];</span><spanclass="w"></span><spanclass="c1">//complete overlap</span>

<spanclass="w"></span><spanclass="k">if</span><spanclass="w"></span><spanclass="p">(</span><spanclass="n">l</span><spanclass="w"></span><spanclass="o">&lt;=</span><spanclass="w"></span><spanclass="n">tl</span><spanclass="w"></span><spanclass="o">&amp;&amp;</span><spanclass="w"></span><spanclass="n">tr</span><spanclass="w"></span><spanclass="o">&lt;=</span><spanclass="w"></span><spanclass="n">r</span><spanclass="p">)</span><spanclass="w"></span><spanclass="k">return</span><spanclass="w"></span><spanclass="n">t</span><spanclass="p">[</span><spanclass="n">v</span><spanclass="p">];</span><spanclass="w"></span><spanclass="c1">//nested segment</span>

<spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">tm</span><spanclass="w"></span><spanclass="o">=</span><spanclass="w"></span><spanclass="p">(</span><spanclass="n">tl</span><spanclass="w"></span><spanclass="o">+</span><spanclass="w"></span><spanclass="n">tr</span><spanclass="p">)</span><spanclass="w"></span><spanclass="o">/</span><spanclass="w"></span><spanclass="mi">2</span><spanclass="p">;</span>

<spanclass="w"></span><spanclass="c1">// partial overlap</span>

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

<spanclass="contributors-text">Contributors:</span>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (76.02%)</li><li><ahref="https://github.com/dasfex"title="dasfex"data-bi-name="contributorprofile"target="_blank">dasfex</a> (5.5%)</li><li><ahref="https://github.com/arjan-bal"title="arjan-bal"data-bi-name="contributorprofile"target="_blank">arjan-bal</a> (4.58%)</li><li><ahref="https://github.com/tpoppo"title="tpoppo"data-bi-name="contributorprofile"target="_blank">tpoppo</a> (1.83%)</li><li><ahref="https://github.com/GaurangTandon"title="GaurangTandon"data-bi-name="contributorprofile"target="_blank">GaurangTandon</a> (1.67%)</li><li><ahref="https://github.com/masterchef2209"title="masterchef2209"data-bi-name="contributorprofile"target="_blank">masterchef2209</a> (1.33%)</li><li><ahref="https://github.com/jxu"title="jxu"data-bi-name="contributorprofile"target="_blank">jxu</a> (1.25%)</li><li><ahref="https://github.com/Stillswarm"title="Stillswarm"data-bi-name="contributorprofile"target="_blank">Stillswarm</a> (0.92%)</li><li><ahref="https://github.com/akoutian"title="akoutian"data-bi-name="contributorprofile"target="_blank">akoutian</a> (0.92%)</li><li><ahref="https://github.com/L1nkus"title="L1nkus"data-bi-name="contributorprofile"target="_blank">L1nkus</a> (0.9199999999999999%)</li><li><ahref="https://github.com/wikku"title="wikku"data-bi-name="contributorprofile"target="_blank">wikku</a> (0.84%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (0.58%)</li><li><ahref="https://github.com/pr4shan7"title="pr4shan7"data-bi-name="contributorprofile"target="_blank">pr4shan7</a> (0.5%)</li><li><ahref="https://github.com/kerolloz"title="kerolloz"data-bi-name="contributorprofile"target="_blank">kerolloz</a> (0.5%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (0.42%)</li><li><ahref="https://github.com/huggin"title="huggin"data-bi-name="contributorprofile"target="_blank">huggin</a> (0.33%)</li><li><ahref="https://github.com/zyrch"title="zyrch"data-bi-name="contributorprofile"target="_blank">zyrch</a> (0.25%)</li><li><ahref="https://github.com/SiddharthEEE"title="SiddharthEEE"data-bi-name="contributorprofile"target="_blank">SiddharthEEE</a> (0.17%)</li><li><ahref="https://github.com/xirc"title="xirc"data-bi-name="contributorprofile"target="_blank">xirc</a> (0.17%)</li><li><ahref="https://github.com/boxlesscat"title="boxlesscat"data-bi-name="contributorprofile"target="_blank">boxlesscat</a> (0.08%)</li><li><ahref="https://github.com/3centroids"title="3centroids"data-bi-name="contributorprofile"target="_blank">3centroids</a> (0.08%)</li><li><ahref="https://github.com/mehrdad3301"title="mehrdad3301"data-bi-name="contributorprofile"target="_blank">mehrdad3301</a> (0.08%)</li><li><ahref="https://github.com/scion03"title="scion03"data-bi-name="contributorprofile"target="_blank">scion03</a> (0.08%)</li><li><ahref="https://github.com/DevChoganwala"title="DevChoganwala"data-bi-name="contributorprofile"target="_blank">DevChoganwala</a> (0.08%)</li><li><ahref="https://github.com/Abhishek-Saini"title="Abhishek-Saini"data-bi-name="contributorprofile"target="_blank">Abhishek-Saini</a> (0.08%)</li><li><ahref="https://github.com/tarptaeya"title="tarptaeya"data-bi-name="contributorprofile"target="_blank">tarptaeya</a> (0.08%)</li><li><ahref="https://github.com/it-is-skywalkerl"title="it-is-skywalkerl"data-bi-name="contributorprofile"target="_blank">it-is-skywalkerl</a> (0.08%)</li><li><ahref="https://github.com/forsythe"title="forsythe"data-bi-name="contributorprofile"target="_blank">forsythe</a> (0.08%)</li><li><ahref="https://github.com/ChangMarkusYu"title="ChangMarkusYu"data-bi-name="contributorprofile"target="_blank">ChangMarkusYu</a> (0.08%)</li><li><ahref="https://github.com/Aryamn"title="Aryamn"data-bi-name="contributorprofile"target="_blank">Aryamn</a> (0.08%)</li><li><ahref="https://github.com/ArthurConmy"title="ArthurConmy"data-bi-name="contributorprofile"target="_blank">ArthurConmy</a> (0.08%)</li><li><ahref="https://github.com/tanmay-sinha"title="tanmay-sinha"data-bi-name="contributorprofile"target="_blank">tanmay-sinha</a> (0.08%)</li><li><ahref="https://github.com/idleft"title="idleft"data-bi-name="contributorprofile"target="_blank">idleft</a> (0.08%)</li><li><ahref="https://github.com/Naman-Bhalla"title="Naman-Bhalla"data-bi-name="contributorprofile"target="_blank">Naman-Bhalla</a> (0.08%)</li><li><ahref="https://github.com/RodionGork"title="RodionGork"data-bi-name="contributorprofile"target="_blank">RodionGork</a> (0.08%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (76.02%)</li><li><ahref="https://github.com/dasfex"title="dasfex"data-bi-name="contributorprofile"target="_blank">dasfex</a> (5.5%)</li><li><ahref="https://github.com/arjan-bal"title="arjan-bal"data-bi-name="contributorprofile"target="_blank">arjan-bal</a> (4.58%)</li><li><ahref="https://github.com/tpoppo"title="tpoppo"data-bi-name="contributorprofile"target="_blank">tpoppo</a> (1.83%)</li><li><ahref="https://github.com/GaurangTandon"title="GaurangTandon"data-bi-name="contributorprofile"target="_blank">GaurangTandon</a> (1.67%)</li><li><ahref="https://github.com/masterchef2209"title="masterchef2209"data-bi-name="contributorprofile"target="_blank">masterchef2209</a> (1.33%)</li><li><ahref="https://github.com/jxu"title="jxu"data-bi-name="contributorprofile"target="_blank">jxu</a> (1.25%)</li><li><ahref="https://github.com/akoutian"title="akoutian"data-bi-name="contributorprofile"target="_blank">akoutian</a> (0.92%)</li><li><ahref="https://github.com/L1nkus"title="L1nkus"data-bi-name="contributorprofile"target="_blank">L1nkus</a> (0.9199999999999999%)</li><li><ahref="https://github.com/wikku"title="wikku"data-bi-name="contributorprofile"target="_blank">wikku</a> (0.84%)</li><li><ahref="https://github.com/Stillswarm"title="Stillswarm"data-bi-name="contributorprofile"target="_blank">Stillswarm</a> (0.83%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (0.6599999999999999%)</li><li><ahref="https://github.com/pr4shan7"title="pr4shan7"data-bi-name="contributorprofile"target="_blank">pr4shan7</a> (0.5%)</li><li><ahref="https://github.com/kerolloz"title="kerolloz"data-bi-name="contributorprofile"target="_blank">kerolloz</a> (0.5%)</li><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (0.42%)</li><li><ahref="https://github.com/huggin"title="huggin"data-bi-name="contributorprofile"target="_blank">huggin</a> (0.33%)</li><li><ahref="https://github.com/zyrch"title="zyrch"data-bi-name="contributorprofile"target="_blank">zyrch</a> (0.25%)</li><li><ahref="https://github.com/SiddharthEEE"title="SiddharthEEE"data-bi-name="contributorprofile"target="_blank">SiddharthEEE</a> (0.17%)</li><li><ahref="https://github.com/xirc"title="xirc"data-bi-name="contributorprofile"target="_blank">xirc</a> (0.17%)</li><li><ahref="https://github.com/boxlesscat"title="boxlesscat"data-bi-name="contributorprofile"target="_blank">boxlesscat</a> (0.08%)</li><li><ahref="https://github.com/3centroids"title="3centroids"data-bi-name="contributorprofile"target="_blank">3centroids</a> (0.08%)</li><li><ahref="https://github.com/mehrdad3301"title="mehrdad3301"data-bi-name="contributorprofile"target="_blank">mehrdad3301</a> (0.08%)</li><li><ahref="https://github.com/scion03"title="scion03"data-bi-name="contributorprofile"target="_blank">scion03</a> (0.08%)</li><li><ahref="https://github.com/DevChoganwala"title="DevChoganwala"data-bi-name="contributorprofile"target="_blank">DevChoganwala</a> (0.08%)</li><li><ahref="https://github.com/Abhishek-Saini"title="Abhishek-Saini"data-bi-name="contributorprofile"target="_blank">Abhishek-Saini</a> (0.08%)</li><li><ahref="https://github.com/tarptaeya"title="tarptaeya"data-bi-name="contributorprofile"target="_blank">tarptaeya</a> (0.08%)</li><li><ahref="https://github.com/it-is-skywalkerl"title="it-is-skywalkerl"data-bi-name="contributorprofile"target="_blank">it-is-skywalkerl</a> (0.08%)</li><li><ahref="https://github.com/forsythe"title="forsythe"data-bi-name="contributorprofile"target="_blank">forsythe</a> (0.08%)</li><li><ahref="https://github.com/ChangMarkusYu"title="ChangMarkusYu"data-bi-name="contributorprofile"target="_blank">ChangMarkusYu</a> (0.08%)</li><li><ahref="https://github.com/Aryamn"title="Aryamn"data-bi-name="contributorprofile"target="_blank">Aryamn</a> (0.08%)</li><li><ahref="https://github.com/ArthurConmy"title="ArthurConmy"data-bi-name="contributorprofile"target="_blank">ArthurConmy</a> (0.08%)</li><li><ahref="https://github.com/tanmay-sinha"title="tanmay-sinha"data-bi-name="contributorprofile"target="_blank">tanmay-sinha</a> (0.08%)</li><li><ahref="https://github.com/idleft"title="idleft"data-bi-name="contributorprofile"target="_blank">idleft</a> (0.08%)</li><li><ahref="https://github.com/Naman-Bhalla"title="Naman-Bhalla"data-bi-name="contributorprofile"target="_blank">Naman-Bhalla</a> (0.08%)</li><li><ahref="https://github.com/RodionGork"title="RodionGork"data-bi-name="contributorprofile"target="_blank">RodionGork</a> (0.08%)</li></ul>