<?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 Sivagiri Visakan on Medium]]></title>
        <description><![CDATA[Stories by Sivagiri Visakan on Medium]]></description>
        <link>https://medium.com/@sivagiri?source=rss-7ed5874b2167------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*utqJREdJzt_xJ2Eo.jpg</url>
            <title>Stories by Sivagiri Visakan on Medium</title>
            <link>https://medium.com/@sivagiri?source=rss-7ed5874b2167------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 02:15:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@sivagiri/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[Dissecting into Segment trees]]></title>
            <link>https://medium.com/@sivagiri/dissecting-into-segment-trees-ee603a4740d3?source=rss-7ed5874b2167------2</link>
            <guid isPermaLink="false">https://medium.com/p/ee603a4740d3</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[data-structures]]></category>
            <dc:creator><![CDATA[Sivagiri Visakan]]></dc:creator>
            <pubDate>Fri, 25 Oct 2019 18:18:51 GMT</pubDate>
            <atom:updated>2019-10-28T10:10:04.187Z</atom:updated>
            <content:encoded><![CDATA[<h3>Exploring Segment Trees</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ESFyirG22uBp-B1bkYZvQQ.png" /></figure><p>Before we get into detail about what segment trees are, we shall see a bit about range queries.</p><h3>A look into range queries</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eLWmHyXuTlmk71-ZsTKrqg.png" /><figcaption>A simple example of a range query</figcaption></figure><p>At times, in a real-time application, we require to query a list of data by range.<br>Some of the typical range queries are <em>minimum in the given range, maximum in the given range, the sum of the given range, </em>etc.</p><p>Consider this example — we have the price of a particular stock for every minute in a particular day, typically with 0th index containing the price at 1st minute, 1st index containing the data in the 2nd minute and so on.</p><p>We may be interested in finding the <em>hourly minimum price</em> for every hour of the day for analyzing the data</p><p>This is an example of a range query where we are querying for the maximum data point in the range of every 60 data points.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*k87Eh_UgXhupu_AsXW6Z0Q.png" /></figure><h3>Approaches to perform a range query</h3><h4><strong>The naive way</strong></h4><ul><li>One approach is that we start traversing the array from the lower limit of the range, and traverse it till the upper limit of the range and calculate the required query.</li><li>This approach works fine for a simple query in a small range, but imagine if the number of queries and the number of elements in the range are huge?<br>The time complexity becomes <em>Ο(mn)<br></em>Our approach doesn’t scale well in this case.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8h9aXj_BbEmAmAvUVDj3yQ.png" /><figcaption>The naive approach</figcaption></figure><h4>Build a 2-D matrix</h4><ul><li>We can build a 2-D matrix, with an entry <em>Aᵢ,ⱼ</em> corresponding to the answer we need in the range from the index <em>i </em>to <em>j.</em></li><li>Then, we can answer a query by just looking up an element in the array. <br>For example, if we need the maximum in the range of the index from 100 to 200, we can directly get the answer by looking up the element A₁₀₀,₂₀₀ in the matrix.</li></ul><p>But the drawback here is that we need <em>O(n</em>²<em>) </em>space to maintain this and <em>O(n</em>²<em>)</em> time initially to build this matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KQV6Qq8ofokz5QAssumC0w.png" /></figure><h4>So can we do something more optimized?</h4><blockquote>The answer is yes, and the answer is Segment trees</blockquote><blockquote><strong>Note: </strong>A basic understanding of trees is recommended.<br>You can find tons of material online for learning about trees.</blockquote><h3>Segment Trees — An Introduction</h3><p>The <strong>segment tree</strong> is based upon the divide-and-conquer paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array’s elements may be efficiently performed.</p><p>Segment trees are constructed using bottom-up approach. So, all the leaf nodes are the actual values of a given array. The internal nodes contain the answer of some operation of their children i.e. if we are in need of a range sum query, then <em>addition </em>is the operation, an internal node has the sum of its children.</p><p>So finally, the root contains the <em>sum</em> of all the elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/638/0*yl8iaNrdgEF-zYMS" /></figure><blockquote>An example sum tree constructed for the list of data</blockquote><blockquote>1,3,5,7,9,11</blockquote><h3>Segment Trees — A look at its representation in memory</h3><p>Similar to heaps, a segment tree is also represented as an array. But the difference here is, it is not a complete binary tree. It is rather a full binary tree (every node has 0 or 2 children) and all levels are filled except possibly the last level. Unlike Heap, the last level may have gaps between the nodes.</p><p>Then what happens to the dummy value in the array? Does this not reduce the space efficiency?</p><p>The dummy values are of no use and not accessed. And it will reduce efficiency. But compared to other methods for solving range queries it is efficient.</p><p>The memory representation of the segment tree example given above is</p><p><strong>{36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}</strong></p><h3>Operations on a segment tree</h3><p>What all operations can be done on a segment tree? Basically the structure can’t be changed i.e we cannot add new nodes in the tree. But we can update the tree or query the tree — which is the motivation to construct such a tree in the first place.</p><p>Segment tree provides two operations:</p><ol><li><strong>Query:</strong> In this operation, we can query on an interval or range and return the answer to the problem (say minimum/maximum/summation in that particular range).</li><li><strong>Update:</strong> To update an element i of the input array A.</li></ol><p><strong>Query:</strong></p><p>Suppose you are given a problem to find the sum of elements in the range [l,r]. First, construct the tree using the above algorithm.</p><p>Now there are three possible cases,</p><ol><li><strong>Case 1:</strong> The range exactly overlaps with the current node’s segment — then the value stored in this node is the required answer.</li><li><strong>Case 2:</strong> The range is completely out of overlap — then we move to the other child for the current node.</li><li><strong>Case 3:</strong> The range is partially overlapped — now we recursively move on one child till it is in range and also on the other child and combining the values would give us the required answer.</li></ol><h4>Let’s look at an example</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/0*AzU7GXzoyZutYPUQ" /><figcaption>Segment tree for <strong><em>[1,3,−2,8,−</em>7<em>]</em></strong></figcaption></figure><blockquote>Let A = [1,3,−2,8,−7] be the given array. Now construct the segment tree.</blockquote><p><strong>Our query</strong>: Find the sum of numbers from index 2 to 4</p><ul><li>Start from the root.</li><li>The range is overlapped but not exactly, so move recursively to both children.</li><li>The right child is exactly overlapped, but the left child is partially overlapped.</li><li>Now move to the child of it and we find it be in range.</li><li>Finally, add both values in the range to give the solution.</li></ul><p>The colored nodes are accessed for this query.</p><h4>Update</h4><p>Suppose that think of a situation where you want to change value in the array. We will, along side, update the constructed segment tree as well to reflect the changes in the array</p><p>Let’s look at the updation of single value in the array.</p><p>To update a value, we basically do a range query. For example, if we wanted to update element with index 2, then we do a query on the range <em>[2,2] </em>to reach the element with index 2 and update it.</p><p>To update the value, traverse till the leaf node recursively and now change the new value and recompute the sum as we have built the tree.</p><p>Let’s see an example for updation of value on the above built tree.</p><p>Example :</p><p>Update a[2]=3.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*7aFeoYcKYchFCvcZ" /></figure><p>The green nodes are the nodes that we visit and update.</p><p>Since you traverse to the leaf and update only its value the complexity is O(logN).</p><h3>Competitive Programming Question</h3><p>After learning about segment trees and how it is efficient in solving range related queries, here is an interesting question to show you the uses of it.</p><h4>Count Correct Bracket Subsequence</h4><p><strong>Question:</strong></p><p>You are given with a bracket sequence or in other words, a string <em>‘S’</em> of length ’n’, consisting of only either ‘(‘ or ‘)’. You have to answer <em>‘m’</em> number of queries. Each query is represented by two integers, say lᵢ rᵢ <em>(1 ≤ l</em>ᵢ<em> ≤ r</em>ᵢ<em> ≤ n)</em>. It basically represents a range. The answer to the ith query is the length of the maximum correct bracket subsequence of the sequence <em>S</em>ₗᵢ<em>, S</em>ₗᵢ₊₁<em>,….., S</em>ᵣᵢ<em>.</em></p><p><em>Note: </em>A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters “1” and “+” between the characters of the string. For example, bracket sequences “()()” and “(())” are correct because the resulting expressions are “(1)+(1)” and “((1+1)+1)” respectively, whereas “)(“ and “(“ are not correct.</p><p><strong>Example:</strong></p><p>Let the bracket sequence be “())(())(“. Let m=3 (Number of queries).</p><p><strong>Query 1:</strong> l₁ r₁ = 1 3</p><p><strong>Output:</strong> 2 &lt; the correct subsequence is “()” &gt;</p><p><strong>Query 2:</strong> l₂ r₂ = 1 8</p><p><strong>Output:</strong> 6 &lt; the correct subsequence is “() (())” &gt;</p><p><strong>Query 3:</strong> l₃ r₃ = 7 8</p><p><strong>Output:</strong> 0 &lt; no correct subsequence &gt;</p><p><strong>Input</strong></p><p>The first line contains a bracket sequence <em>S</em>₁<em>, S</em>₂<em>,….., S</em>ₙ <em>(1 ≤ n ≤ 106) </em>without any spaces<em>.</em></p><p>The second line contains an integer <em>m (1 ≤ m ≤ 105)</em> — the number of queries.</p><p>Each of the next <em>m</em> lines contains a pair of integers.</p><p>The ith line contains integers<em> l</em>ᵢ<em> r</em>ᵢ<em> (1 ≤ l</em>ᵢ<em> ≤ r</em>ᵢ<em> ≤ n)</em> — the description of the <em>i-th</em> query.</p><p><strong>Output</strong></p><p>Print the answer to each question on a single line. Print the answers in the order of the input.</p><blockquote>We strongly recommend that you attempt a solution for this problem on your own before proceeding to the solution.</blockquote><blockquote>This problem can be found on <a href="https://codeforces.com/problemset/problem/380/C">Codeforces</a></blockquote><h4><strong>Solution</strong></h4><p>We have the question in hand. Now the problem is to model the solution and find what values are to be stored in a node in our segment tree.</p><p>We have to find the longest correct bracket sequence in a given range. For a given range, we can find the length of correct bracket sequence in linear time. If we employ this method for every query, the total time would be much more. So we have to reduce the complexity. In a segment tree node we store three values,</p><p>a — Length of the longest correct subsequence</p><p>b — Number open brackets without a match</p><p>c — Number of closing brackets without a match</p><p>The node <em>i </em>whose children are j and k will have the following values,</p><p>aᵢ = aⱼ+aₖ+t</p><p>bᵢ = bⱼ+bₖ-t</p><p>cᵢ = cⱼ+cₖ-t</p><p>where t = min(bⱼ,cₖ).</p><p>The idea behind is that the longest correct subsequence of a sequence 1, will also be present in a largest correct subsequence of sequence 2, that has sequence 1 in it. It also contains extra elements.</p><p>The unmatched brackets in the left(‘(‘) are matched to unmatched brackets in right (‘)‘) to form a correct sequence.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b7875f4bba6b2717b56420b6e6001a1c/href">https://medium.com/media/b7875f4bba6b2717b56420b6e6001a1c/href</a></iframe><p>Thank you for reading! 😃<br>We hope that you have got the basic idea behind segment trees!</p><blockquote>Written by<br><em>Basheer Ahamed<br>Vinay Kumar<br>Kaushik Ram<br>Sangeetha<br>Sivagiri Visakan</em></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ee603a4740d3" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>