{"id":116229,"date":"2026-06-16T23:00:20","date_gmt":"2026-06-16T17:30:20","guid":{"rendered":"https:\/\/www.guvi.in\/blog\/?p=116229"},"modified":"2026-06-16T23:00:21","modified_gmt":"2026-06-16T17:30:21","slug":"segment-trees-and-fenwick-trees","status":"publish","type":"post","link":"https:\/\/www.guvi.in\/blog\/segment-trees-and-fenwick-trees\/","title":{"rendered":"Segment Trees and Fenwick Trees Explained"},"content":{"rendered":"\n<p>When working with large arrays, repeatedly calculating range sums and handling updates using brute force becomes inefficient. Segment Trees and Fenwick Trees solve this by supporting both range queries and point updates in <strong>O(log n)<\/strong> time. These data structures are essential tools for DSA interviews, competitive programming, and high-performance applications.&nbsp;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Quick TL;DR<\/strong><\/h2>\n\n\n\n<ul>\n<li>Segment Trees and Fenwick Trees (Binary Indexed Trees) are efficient data structures used for range queries and point updates in <strong>O(log n)<\/strong> time. <\/li>\n\n\n\n<li>Segment Trees offer greater flexibility, supporting various query types and range updates, while Fenwick Trees are simpler, more memory-efficient, and ideal for prefix-sum operations. <\/li>\n\n\n\n<li>Both are widely used in competitive programming and commonly asked about in technical interviews.\u00a0<\/li>\n<\/ul>\n\n\n\n<p><em>Want to master segment trees, Fenwick trees, graphs, and all advanced DSA topics with real interview prep and coding projects? Check out <strong>HCL GUVI&#8217;s<\/strong><a href=\"https:\/\/www.guvi.in\/courses\/programming\/dsa-using-python\/?utm_source=blog&amp;utm_medium=hyperlink&amp;utm_campaign=Segment+Trees+and+Fenwick+Trees+Explained\" target=\"_blank\" rel=\"noreferrer noopener\"><strong> Data Structures &amp; Algorithms Programme<\/strong> <\/a>built for students and professionals who want to crack top product-based company interviews.<\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is a Segment Tree?<\/strong><\/h2>\n\n\n\n<p>A segment tree is a binary tree built over an array where each node stores an aggregate value, typically sum, min, or max, for a contiguous segment of the array. The root covers the entire array. Each node splits its range in half: the left child covers the left half, and the right child covers the right half. The leaf nodes each represent a single element.<\/p>\n\n\n\n<p>For an array of n elements, the segment tree has at most 4n nodes and occupies O(n) space. Building it takes O(n log n) time.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Building a Segment Tree<\/strong><\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>def build(arr, tree, node, start, end):\n\n&nbsp;&nbsp;&nbsp;&nbsp;if start == end:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tree&#91;node] = arr&#91;start] &nbsp; # leaf node\n\n&nbsp;&nbsp;&nbsp;&nbsp;else:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid = (start + end) \/\/ 2\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;build(arr, tree, 2*node, &nbsp; start, mid)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;build(arr, tree, 2*node+1, mid+1, end)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tree&#91;node] = tree&#91;2*node] + tree&#91;2*node+1]<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Range Query:O(log n)<\/strong><\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>def query(tree, node, start, end, l, r):\n\n&nbsp;&nbsp;&nbsp;&nbsp;if r &lt; start or end &lt; l:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # segment outside range\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return 0\n\n&nbsp;&nbsp;&nbsp;&nbsp;if l &lt;= start and end &lt;= r: &nbsp; &nbsp; &nbsp; # segment fully inside range\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return tree&#91;node]\n\n&nbsp;&nbsp;&nbsp;&nbsp;mid = (start + end) \/\/ 2 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # partial overlap \u2014 go deeper\n\n&nbsp;&nbsp;&nbsp;&nbsp;left&nbsp; = query(tree, 2*node, &nbsp; start, mid, &nbsp; l, r)\n\n&nbsp;&nbsp;&nbsp;&nbsp;right = query(tree, 2*node+1, mid+1, end, &nbsp; l, r)\n\n&nbsp;&nbsp;&nbsp;&nbsp;return left + right<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Point Update: O(log n)<\/strong><\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>def update(tree, node, start, end, idx, val):\n\n&nbsp;&nbsp;&nbsp;&nbsp;if start == end:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tree&#91;node] = val\n\n&nbsp;&nbsp;&nbsp;&nbsp;else:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid = (start + end) \/\/ 2\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if idx &lt;= mid:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; update(tree, 2*node, &nbsp; start, mid, &nbsp; idx, val)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; update(tree, 2*node+1, mid+1, end, &nbsp; idx, val)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tree&#91;node] = tree&#91;2*node] + tree&#91;2*node+1]<\/code><\/pre>\n\n\n\n<p><strong>Read More: <\/strong><a href=\"https:\/\/www.guvi.in\/blog\/introduction-to-tree-data-structure\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>What is a Tree Data Structure?<\/strong><\/a><\/p>\n\n\n\n<p>Want to master segment trees, Fenwick trees, graphs, and all advanced DSA topics with real interview prep and coding projects? Check out <strong>HCL GUVI&#8217;s<\/strong><a href=\"https:\/\/www.guvi.in\/courses\/programming\/dsa-using-python\/?utm_source=blog&amp;utm_medium=hyperlink&amp;utm_campaign=Segment+Trees+and+Fenwick+Trees+Explained\" target=\"_blank\" rel=\"noreferrer noopener\"><strong> Data Structures &amp; Algorithms Programme<\/strong> <\/a>built for students and professionals who want to crack top product-based company interviews.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is a Fenwick Tree (Binary Indexed Tree)?<\/strong><\/h2>\n\n\n\n<p>A Fenwick tree, also called a Binary Indexed Tree (BIT), is a flat array that cleverly uses the binary representation of indices to store partial sums. Each index i in the BIT is responsible for storing the sum of a specific range of elements, determined by the lowest set bit (LSB) of i.<\/p>\n\n\n\n<p>Compared to a segment tree, a Fenwick tree uses less memory (just n+1 integers), has a smaller constant factor, and is faster in practice, but it only natively supports prefix sum queries and point updates. It cannot directly support range min\/max queries like a segment tree can.<\/p>\n\n\n\n<p>&nbsp;<strong>Fenwick Tree Update and Prefix Query<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>class FenwickTree:\n\n&nbsp;&nbsp;&nbsp;&nbsp;def __init__(self, n):\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.n = n\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.tree = &#91;0] * (n + 1)&nbsp; # 1-indexed\n\n&nbsp;&nbsp;&nbsp;&nbsp;def update(self, i, delta): # add delta to index i \u2014 O(log n)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while i &lt;= self.n:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; self.tree&#91;i] += delta\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i += i &amp; (-i)&nbsp; &nbsp; &nbsp; # move to parent using LSB\n\n&nbsp;&nbsp;&nbsp;&nbsp;def prefix_sum(self, i): &nbsp; # sum of &#91;1..i] \u2014 O(log n)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;total = 0\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while i &gt; 0:\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; total += self.tree&#91;i]\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i -= i &amp; (-i)&nbsp; &nbsp; &nbsp; # move to predecessor using LSB\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return total\n\n&nbsp;&nbsp;&nbsp;&nbsp;def range_sum(self, l, r): # sum of &#91;l..r] \u2014 O(log n)\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return self.prefix_sum(r) - self.prefix_sum(l - 1)<\/code><\/pre>\n\n\n\n<div style=\"background-color: #099f4e; border: 3px solid #110053; border-radius: 12px; padding: 18px 22px; color: #FFFFFF; font-family: Montserrat, Helvetica, sans-serif; line-height: 1.6; box-shadow: 0 4px 12px rgba(0, 0, 0, 0.15); max-width: 800px;\">\n  <strong style=\"font-size: 22px; color: #FFFFFF;\">\ud83d\udca1 Did You Know?<\/strong>\n  <p style=\"margin-top: 14px;\">\n    The <strong>Fenwick Tree<\/strong>, also known as the <strong>Binary Indexed Tree (BIT)<\/strong>, was introduced by \n    :contentReference[oaicite:0]{index=0} in 1994 in his paper <em>\u201cA New Data Structure for Cumulative Frequency Tables\u201d<\/em>. It is a highly efficient data structure designed to compute prefix sums and perform point updates in logarithmic time. The core idea relies on bit manipulation\u2014specifically using the <strong>lowest set bit<\/strong> of an index to determine the range of responsibility for each node. This clever design reduces prefix sum queries from <strong>O(n)<\/strong> to <strong>O(log n)<\/strong>, enabling fast updates and queries with a compact and elegant implementation widely used in competitive programming and range query problems.\n  <\/p>\n<\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Real-World Use Cases<\/strong><\/h2>\n\n\n\n<p>Both segment trees and Fenwick trees appear in competitive programming, databases, and systems that need efficient range queries over mutable data.<\/p>\n\n\n\n<ul>\n<li><strong>Stock price range queries:<\/strong> Find the minimum or maximum stock price between two timestamps in O(log n) using a segment tree.<\/li>\n\n\n\n<li><strong>Frequency tables and rankings:<\/strong> Count inversions in an array, maintain a leaderboard, or compute the rank of a value classic Fenwick tree applications.<\/li>\n\n\n\n<li><strong>2D range sum queries:<\/strong> Both trees extend to 2D for image processing, matrix prefix sums, and game maps using a 2D BIT or 2D segment tree.<\/li>\n\n\n\n<li><strong>Interval scheduling and overlap detection:<\/strong> Segment trees with lazy propagation handle range-mark and range-query operations for booking systems and calendar conflict detection.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Common Mistakes When Working with These Trees<\/strong><\/h2>\n\n\n\n<p><strong>1. Off-by-one errors in indexing: <\/strong>Segment trees typically use 1-based indexing with the tree array sized to 4n. Fenwick trees are always 1-indexed. Mixing 0-based and 1-based indexing within the same implementation is the most common source of wrong answers.<\/p>\n\n\n\n<p><strong>2. Forgetting lazy propagation for range updates: <\/strong>A basic segment tree only supports point updates. If you need to add a value to all elements in a range, you must implement lazy propagation, a deferred update mechanism. Skipping this causes O(n) range updates instead of O(log n).<\/p>\n\n\n\n<p><strong>3. Using a segment tree where a Fenwick tree suffices: <\/strong>For pure prefix sum and point update problems, a Fenwick tree is simpler to implement, uses less memory, and runs faster. Reaching for a segment tree by default adds unnecessary complexity when the problem only requires prefix sums.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>Segment trees and Fenwick trees both solve the same core problem: efficient range queries on mutable arrays but with different trade-offs. The segment tree is more powerful, supporting range min\/max, range updates with lazy propagation, and arbitrary associative operations. The Fenwick tree is leaner and faster for prefix sum problems, with remarkably concise code once you understand the LSB trick. The best way to learn both is to implement a range sum query from scratch using each structure, then extend your segment tree to support range minimum and finally lazy propagation.&nbsp;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>FAQ<\/strong><\/h2>\n\n\n<div id=\"rank-math-faq\" class=\"rank-math-block\">\n<div class=\"rank-math-list \">\n<div id=\"faq-question-1781238734034\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">1. <strong>What is a segment tree in DSA?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>A segment tree is a binary tree built over an array where each node stores an aggregate value sum, min, or max for a contiguous segment. It supports both range queries and point updates in O(log n) time, making it far more efficient than brute-force recomputation for problems with many queries on a mutable array.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781238748105\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">2. <strong>What is a Fenwick tree (Binary Indexed Tree)?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>A Fenwick tree, or Binary Indexed Tree, is a flat array that uses the binary representation of indices to store partial sums efficiently. It supports prefix sum queries and point updates in O(log n) time using simple bit manipulation, with less memory and lower constant factor than a segment tree.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781238761660\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">3. <strong>What is the difference between a segment tree and a Fenwick tree?<\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>A segment tree is more flexible it supports range min\/max queries, range updates with lazy propagation, and arbitrary associative operations. A Fenwick tree is simpler, uses less memory, and is faster in practice but natively supports only prefix sum queries and point updates.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781238830164\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">4. <strong>What is the time complexity of segment trees and Fenwick trees? <\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>Both data structures support O(log n) range queries and O(log n) point updates. Building a segment tree takes O(n) time; building a Fenwick tree takes O(n log n). A segment tree uses O(4n) space; a Fenwick tree uses O(n) space.<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781238856371\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">5. <strong>What is lazy propagation in a segment tree? <\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>Lazy propagation is a technique that defers range updates in a segment tree. Instead of updating every element in a range immediately, which would cost O(n), the update is stored at the highest relevant node and propagated down only when a child node is actually accessed. This keeps range updates at O(log n).<\/p>\n\n<\/div>\n<\/div>\n<div id=\"faq-question-1781238879220\" class=\"rank-math-list-item\">\n<h3 class=\"rank-math-question \">6. <strong>What is the lowest set bit trick in a Fenwick tree? <\/strong><\/h3>\n<div class=\"rank-math-answer \">\n\n<p>The lowest set bit (LSB) of an index i, computed as i &amp; (-i), determines which range each BIT position is responsible for. During update, adding the LSB moves you to the next responsible parent.\u00a0<\/p>\n\n<\/div>\n<\/div>\n<\/div>\n<\/div>","protected":false},"excerpt":{"rendered":"<p>When working with large arrays, repeatedly calculating range sums and handling updates using brute force becomes inefficient. Segment Trees and Fenwick Trees solve this by supporting both range queries and point updates in O(log n) time. These data structures are essential tools for DSA interviews, competitive programming, and high-performance applications.&nbsp; Quick TL;DR Want to master [&hellip;]<\/p>\n","protected":false},"author":63,"featured_media":117066,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17],"tags":[],"views":"37","authorinfo":{"name":"Vishalini Devarajan","url":"https:\/\/www.guvi.in\/blog\/author\/vishalini\/"},"thumbnailURL":"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2026\/06\/segment-trees-and-fenwick-trees-300x115.webp","_links":{"self":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/116229"}],"collection":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/users\/63"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/comments?post=116229"}],"version-history":[{"count":3,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/116229\/revisions"}],"predecessor-version":[{"id":117067,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/posts\/116229\/revisions\/117067"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/media\/117066"}],"wp:attachment":[{"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/media?parent=116229"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/categories?post=116229"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guvi.in\/blog\/wp-json\/wp\/v2\/tags?post=116229"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}