<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Bruno Papa on Medium]]></title>
        <description><![CDATA[Stories by Bruno Papa on Medium]]></description>
        <link>https://medium.com/@brpapa?source=rss-acd64d1be667------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*ghgx-cPJrBPWHn-b3B3rtQ.jpeg</url>
            <title>Stories by Bruno Papa on Medium</title>
            <link>https://medium.com/@brpapa?source=rss-acd64d1be667------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 19:17:57 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@brpapa/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[My Recursion Tree Visualizer project went viral on Linkedin]]></title>
            <link>https://brpapa.medium.com/my-recursion-tree-visualizer-project-went-viral-on-linkedin-157063844ea2?source=rss-acd64d1be667------2</link>
            <guid isPermaLink="false">https://medium.com/p/157063844ea2</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[react]]></category>
            <dc:creator><![CDATA[Bruno Papa]]></dc:creator>
            <pubDate>Wed, 14 Oct 2020 18:34:44 GMT</pubDate>
            <atom:updated>2020-10-14T18:34:44.835Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OYUVkY2Qy1UD64OQ5ZLhLA.jpeg" /></figure><p>Recently I finished my favorite side project by now.</p><p>It is a Recursion Tree Visualizer that helps programmers understand recursion. You input any recursive function using javascript code and visualize your corresponding recursion tree.</p><p>I first published this in my Linkedin profile and I was surprised by the quick engagement that the <a href="https://www.linkedin.com/feed/update/urn:li:activity:6716531439292211200/">post</a> generated.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HSTArSWsQLDvbGodbfU-Pg.png" /></figure><p>More than 20K views and more than 1.5K likes in just a few days 🤯.<br> <br>If you want just to try it out, access <a href="https://recursion.now.sh/">https://recursion.now.sh</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=157063844ea2" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Árvore de Segmentos com RMQ (Range Minimum Query)]]></title>
            <link>https://brpapa.medium.com/%C3%A1rvore-de-segmentos-46e4345db716?source=rss-acd64d1be667------2</link>
            <guid isPermaLink="false">https://medium.com/p/46e4345db716</guid>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Bruno Papa]]></dc:creator>
            <pubDate>Mon, 30 Dec 2019 05:14:13 GMT</pubDate>
            <atom:updated>2020-05-10T20:31:10.434Z</atom:updated>
            <content:encoded><![CDATA[<h4>Entenda, de maneira amigável, as motivações e casos de uso dessa incrível estrutura de dados.</h4><p>Uma árvore de segmentos é uma representação de segmentos de um vetor em uma <strong>árvore binária</strong> para que consultas em um dado segmento possam ser feitas de forma eficiente com complexidade de tempo O(log(N)), uma vantagem importante, visto que N pode ser excessivamente grande.</p><p>Mas é importante deixar claro que:</p><blockquote>O custo de sua implementação só compensa os seus ganhos se o vetor for frequentemente<strong> atualizado</strong> e <strong>várias consultas</strong> sejam requeridas.</blockquote><p>Antes de entender minha implementação, considere que:</p><ul><li>Nos foi dado um vetor arr de tamanho N.</li><li>A árvore binária é armazenada como um <strong>vetor</strong> bt de tamanho 4*N, onde 0 é o índice da raiz, bt[v] o valor do vértice <strong>v</strong>, e bt[v*2+1] e bt[v*2+2] o valor de seus filhos à esquerda e à direita, respectivamente.</li></ul><p>Está confuso? Calma! Abaixo vamos aplicá-la à uma RMQ para entender seu funcionamento de forma visual antes de ir para o código.</p><h3>Range Minimum Query (RMQ)</h3><p>Dado um vetor arr, encontre o menor valor no sub-vetor {arr[i], …, arr[j]}, sendo 0 &lt; i ≤ j&lt; N.</p><h4>build bt</h4><p>A raiz, bt[0], representa o segmento <strong>[0 .. N-1] </strong>de arr. Para cada vértice representante de um segmento <strong>[l .. r]</strong>, divide-o em dois segmentos menores: <strong>[l .. (l+r)/2]</strong> e <strong>[(l+r)/2+1 .. r]</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RSp40bSa4qdAODqvvvTkZg.png" /><figcaption>Exemplo da árvore de segmentos, após buildBT, com arr = {18, 17, 13, 19, 15, 11, 20} e N = 7.</figcaption></figure><p>Executamos bt.assign(4*N,0) e, em seguida, chamamos buildBT(0, 0, N-1) para construir os valores iniciais da nossa árvore de segmentos em O(N*log(N)).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/349701fc29464dd5ea52dba65a04e3b7/href">https://medium.com/media/349701fc29464dd5ea52dba65a04e3b7/href</a></iframe><h4>range query</h4><p>Como o algoritmo divide intervalos sucessivamente, conseguimos consultar um intervalo qualquer em complexidade de tempo O(log(N)).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5de4f78e77f8f57a651bed2e4bc2dc21/href">https://medium.com/media/5de4f78e77f8f57a651bed2e4bc2dc21/href</a></iframe><p>Por exemplo, observe que rangeQuery(0, 0, N-1, 1, 3) nos retornará 13, como descrito no diagrama abaixo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oFfcsXOVo0KN7uusD9PNuw.png" /><figcaption>Árvore de recursão para rangeQuery(0, 0, N-1, 1, 3)</figcaption></figure><h4>point update</h4><p>Caso o vetor arr mude em alguma posição i, basta usar as mesmas ideias utilizadas acima para atualizar bt em O(log(N)).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cbde1246ed268b1466850de19d96627e/href">https://medium.com/media/cbde1246ed268b1466850de19d96627e/href</a></iframe><p>Por hoje é só. Vimos que uma árvore de segmentos nos permite fazer consultas eficientes, mas sua implementação é recursiva e, por isso, é preciso estar atento à muitos detalhes.<br>Agradeço a sua leitura, e espero que eu tenha contribuído em, pelo menos, colocar dúvidas na sua cabeça.</p><h3>Referências bibliográficas</h3><ul><li>HALIM, Steven. HALIM, Felix. Competitive Programming 3: &quot;the new lower bound of programming contests&quot;. Chapter 2.4.3. 2013.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=46e4345db716" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>