Range queries and the segment idea in Python

Why it matters

Many programs ask the same kind of question again and again. "What is the total of the items from position l to position r?" The data also changes between the questions. A game scoreboard is a good example. The scores change during a match, and the coach keeps asking for the total of players 10 to 50. A segment tree answers both kinds of request in O(log n) time, which means the work grows very slowly as the list gets longer.

This lesson builds the idea from nothing. You will see the two simple methods that people try first, see exactly where each one breaks, and then meet the structure that fixes the problem. Each program is complete and uses only the standard library, so you can press Run and see what it prints.

Words you need first

A list in Python is a row of boxes. Each box holds one value and has a number called an index. The first index is 0. So the list [1, 3, 5, 7, 9, 11] has six boxes, and the box at index 2 holds 5.

A range is a block of neighbouring boxes. The range from index 1 to index 3 has three boxes: indexes 1, 2 and 3. In this module both ends of a range are included. Every range is written [l..r], where l is the left end and r is the right end. Python slices work differently, because a[1:3] stops before index 3. This lesson does not use slices for ranges, so keep the two rules apart.

A query is a question about the data. A sum query asks for the total of a range. An update changes one box.

Big O describes how the work grows when the input grows. O(n) means the work grows in step with the number of items n. O(log n) means the work grows much more slowly. Doubling n adds only one more step.

The problem, stated plainly

Think about a list of numbers and two kinds of request. The first request is a query: "give me the sum of the numbers from l to r." The second request is an update: "change the number at index i to value." A good structure should handle both kinds of request quickly. Here is the full task in short form:

• query(l, r) returns the sum of the items from index l to index r, both included.
• update(i, value) replaces the item at index i with value.

If you only ever query, the problem is easy. If you only ever update, the problem is also easy. The difficulty comes from mixing the two, and that is where you need the new structure.

Attempt one: add the items in a loop

The simplest solution is a loop. To answer query(l, r), start at l, add each item, and stop at r. Here is a complete program. It takes the list and the range as fixed values and prints both ways of getting the sum.

The program prints:

brute force: 15
prefix sums: 15
prefix array: [0, 1, 4, 9, 16, 25, 36]

The loop works, and it is easy to read. Its cost is the problem. For a range of k items it does k additions. In the worst case the range is the whole list, so one query costs O(n). An update is cheap, though. Changing one box is one assignment, so an update costs O(1), which means it takes a fixed amount of work no matter how long the list is.

Here is what that means in numbers. Suppose the list has one million items and the program answers one million queries, each covering the whole list. That is about 10^12 additions. A modern computer does roughly a few billion simple steps per second, so that would take many minutes. In Python each step is slower than that, because the interpreter does extra work for every addition. The loop is fine for a few hundred items and hopeless for a million.

Attempt two: prefix sums

A prefix sum list stores the running total. Let prefix[i] be the sum of the first i items, which means the items at indexes 0 to i - 1. Then prefix[0] is 0 because there are no items, prefix[1] is the first item, and so on. The total of the range l to r is the difference of two prefix values:

sum(l..r) = prefix[r + 1] - prefix[l]

Why does this work? prefix[r + 1] holds the sum of everything up to index r. prefix[l] holds the sum of everything before index l. Subtracting the second from the first leaves exactly the items from l to r.

Take the list [1, 3, 5, 7, 9, 11]. Its prefix list is [0, 1, 4, 9, 16, 25, 36]. To find the sum from index 1 to index 3, compute prefix[4] - prefix[1], which is 16 - 1 = 15. That is 3 + 5 + 7. The answer takes one subtraction no matter how long the range is, so a query costs O(1).

The first program above already used this idea. The line prefix[r + 1] - prefix[l] is the whole query. Building the prefix list takes one loop over the list, which is O(n) and happens only once.

Prefix sums have a weakness. Think about what happens when one item changes. Say you change the item at index 1 from 3 to 10. Every prefix value from prefix[2] onward includes that item, so every one of those values must be rewritten. In the worst case, when you change the first item, that is all n prefix values. So an update costs O(n).

The second program shows this cost. It changes one item and counts how many prefix values changed.

The output is:

prefix cells that changed: 5
new prefix total: 43

Prefix sums before the change (index 1 goes from 3 to 10):
 
  index:   0   1   2   3   4   5   6
  before:  0   1   4   9  16  25  36
  after:   0   1  11  16  23  32  43
                  ^   ^   ^   ^   ^
                  five cells changed, from index 2 onward

Changing index 1 changed five prefix cells, from index 2 to index 6. The change is bigger in a longer list. If you change index 0 of a list with a million items, almost a million prefix cells change. Prefix sums are the right answer for a list that never changes. They are the wrong answer for a list that changes often.

Comparing the three methods

The table shows the cost of each method. The third row is the structure this module is about.

Read the table as a trade-off. The loop puts all the cost on queries. Prefix sums put all the cost on updates. A segment tree spreads the cost evenly, so neither kind of request is slow. For a list of one million items, log2(n) is about 20. A query then takes around 20 steps, not a million.

The big idea: a tree of segments

A segment is a stretch of the list from one index to another. A segment tree stores the answer for many segments at once. It is a binary tree, which means each node has at most two children. Here is an everyday picture.

Think about a company that tracks sales. Each salesperson has a number. Each team adds up its people. Each department adds up its teams. The company adds up its departments. The company total is a sum of department totals, and each department total is a sum of team totals.

Now ask two questions. First, when one salesperson changes their number, what has to change? Only the totals above them: their team, their department and the company total. The other teams and departments do not need to be touched. Second, when you want the total for teams 3 to 5, what do you add? You do not add every person in those teams. You add the ready-made team totals, and you may use a department total if that department lies entirely inside your range. The answer is built from a few large pieces, not many small ones.

A segment tree works the same way. Each node is one segment and stores the answer for that segment. The root covers the whole list. Its two children cover the left half and the right half. Each child splits again, and the splitting stops when a segment holds one item. Those single-item segments are the leaves.

The tree for [1, 3, 5, 7, 9, 11] has this shape. Each box shows the range of indexes it covers and the sum of those items.

[0..5] = 36                        root
├── [0..2] = 9                     left child
│   ├── [0..1] = 4
│   │   ├── [0] = 1                leaf
│   │   └── [1] = 3                leaf
│   └── [2] = 5                    leaf
└── [3..5] = 27                    right child
    ├── [3..4] = 16
    │   ├── [3] = 7                leaf
    │   └── [4] = 9                leaf
    └── [5] = 11                   leaf

Look at the root. It covers [0..5], all six items, and its sum is 36. Its left child covers [0..2], which is the first three items. Its sum is 1 + 3 + 5 = 9. Its right child covers [3..5] and has sum 7 + 9 + 11 = 27. The two children add to 36, as they should.

Each node has a clear rule. Its left child covers the left half of its range and its right child covers the right half. The split point is the middle, computed as mid = (l + r) // 2. The double slash // is Python's floor division. It divides and drops the fraction, so (0 + 5) // 2 is 2, not 2.5. The left child covers l to mid. The right child covers mid + 1 to r. Notice that mid is in the left child and mid + 1 starts the right child. Nothing is counted twice and nothing is skipped.

Trace a walk through the tree by hand. Start at the root and go down the left side first. Visit [0..2], then [0..1], then the leaf [0]. Come back up, visit the leaf [1], and come back up again to [2]. Then go down the right side in the same way. Each node is visited once. The tree has about 2n nodes, so a walk over all of them costs O(n). A query, by contrast, will visit only a small part of the tree, as you will see in the next lesson.

What each node stores

Every node stores one number, the answer for its segment. For a sum tree that number is the sum. For a minimum tree it would be the smallest value in the segment. The number is not chosen at random. It is always the combination of the two child answers. A sum node is the sum of its children. A minimum node is the smaller of its children.

Leaves are special because they have no children. A leaf covers exactly one index, so its stored number is simply the item at that index. For example, the leaf for index 3 holds 7, and the leaf for index 4 holds 9. Every other node is built from the leaves below it.

The shape of the tree depends only on the number of items. It does not depend on the values. Two lists with the same length always produce trees with the same shape. This is useful later, when you update a value. The path from the root to the changed leaf is always the same kind of path.

The height of the tree is about log2(n). The height is the number of steps from the root to the lowest level. Each step halves the segment, so a tree over a million items is about 20 levels tall. A walk from the top to any leaf takes about 20 steps. That is why queries and updates are fast.

Storing the tree in a list

A tree is not the only way to store a segment tree. Python programs usually store it in a flat list, because lists are fast and simple. The idea comes from the heap structure you may already know. The root goes in slot 1. Slot 0 is left unused. A node in slot i has its left child in slot 2 * i and its right child in slot 2 * i + 1.

The picture below shows the first seven slots of the list. The sum 9 sits in slot 2 because [0..2] is the left child of the root. Its children sit in slots 4 and 5, which are 2 * 2 and 2 * 2 + 1. The sum 27 sits in slot 3, and its children sit in slots 6 and 7. You never need to store pointers. The arithmetic gives the position of every child.

slot:   1      2      3      4      5      6      7
value:  36     9      27     4      5      16     11
range:  [0..5] [0..2] [3..5] [0..1] [2]    [3..4] [5]

Now comes an important question. How big should the list be? A tree over n items can have a lowest level that is not full. The indexes of the lowest nodes can then be much bigger than 2n. The third program prints the largest slot used for each size from 1 to 10.

The output is:

n=1 largest index 1 (needs 2 slots), 2n=2, 4n=4
n=2 largest index 3 (needs 4 slots), 2n=4, 4n=8
n=3 largest index 5 (needs 6 slots), 2n=6, 4n=12
n=4 largest index 7 (needs 8 slots), 2n=8, 4n=16
n=5 largest index 9 (needs 10 slots), 2n=10, 4n=20
n=6 largest index 13 (needs 14 slots), 2n=12, 4n=24
n=7 largest index 13 (needs 14 slots), 2n=14, 4n=28
n=8 largest index 15 (needs 16 slots), 2n=16, 4n=32
n=9 largest index 17 (needs 18 slots), 2n=18, 4n=36
n=10 largest index 25 (needs 26 slots), 2n=20, 4n=40

Look at n=6. The largest slot is 13, so you need 14 slots. The value 2n is only 12, which is too small. A list of length 12 has indexes 0 to 11, and index 13 does not exist. That is why the safe choice is 4 * n. It is always big enough, and it wastes only a constant factor of memory.

The memory cost is simple to state. With 4 * n slots, a sum tree over one million items holds about four million references. On 64-bit CPython, a list of 4,000,000 zeros reports sys.getsizeof of 32000056 bytes, which is about 32 megabytes for the list itself. The exact number depends on the Python build and the machine, so your number may differ. Each int object that is not a small cached value adds its own memory on top.

Building the tree in code

The tree is built by a recursive function. Recursion means a function calls itself on a smaller problem. Here the big problem is "build the segment [l..r]". The smaller problems are "build the left half" and "build the right half". The function stops at a leaf, where the segment holds one item.

The steps are these. If l equals r, copy a[l] into the node. Otherwise compute mid, build the left child, build the right child, and then set the node to the sum of its two children. The children must be built before the parent, because the parent needs their sums.

The next program prints each node as it finishes. It uses the same recursive build you will use in the next lesson.

The output is:

      node 8 [0..0] = 1
      node 9 [1..1] = 3
    node 4 [0..1] = 4
    node 5 [2..2] = 5
  node 2 [0..2] = 9
      node 12 [3..3] = 7
      node 13 [4..4] = 9
    node 6 [3..4] = 16
    node 7 [5..5] = 11
  node 3 [3..5] = 27
node 1 [0..5] = 36

Read the output from top to bottom and you see the order in which the nodes finished. The leaves print first, because they have no children to wait for. Then their parents print, and the root prints last with the total 36. The indentation shows the depth. Each extra level of depth adds two spaces, so the leaves sit furthest to the right. The expression " " * depth builds the indent by repeating a string, which is the same trick you use for any repeated text in Python.

Notice the node numbers. The leaf for index 0 is node 8, and it is the left child of node 4. Node 4 is the left child of node 2, and node 2 is the left child of the root. Each number is double its parent, plus 0 or 1. The numbers are the same numbers that the list layout uses.

What happens inside Python

It helps to picture what the interpreter does with build(1, 0, 5, 0). The interpreter keeps a call stack, which is a list of function calls that are still running. Each call gets its own frame, a small block of memory that holds its parameters and local variables. When build calls itself, the new call sits on top of the stack. When a call finishes, its frame is removed and control returns to the call below it.

For the six-item tree, the stack reaches a depth of about four. The root call waits for its left child. That call waits for its own left child, and so on, down to a leaf. The leaf finishes, and the call below it resumes and calls its right child. This is why the output prints the leaves first. The stack unwinds from the bottom up, and each parent finishes only after both children return.

Python limits how deep this stack may grow. The limit is stored in sys.getrecursionlimit(), and its default value is 1000. A segment tree over a million items is only about 20 levels deep, so the limit is not a problem for trees. It matters when a recursive function goes deep by mistake, as the empty-list example below shows.

The lists take up memory too. a holds the input and tree holds the nodes. The build only writes new numbers into tree. The cost is one visit per node, which is O(n) for the whole build.

Common mistakes

Using prefix sums when the data changes. Prefix sums are fast to query. If the data changes between queries, each change forces a rewrite of many prefix values. Use a segment tree for data that changes.

Making the tree list too small. The usual mistake is [0] * n or [0] * (2 * n). If you then read or write a slot past the end, Python stops the program and prints an error like this:

Traceback (most recent call last):
  File "example.py", line 2, in <module>
    tree[13] = 5
    ~~~~^^^^
IndexError: list assignment index out of range

The last line names the exception, which is the kind of error. Here it says that the index was out of range for the list. The lines above it show the file and the line number where the bad index was used. The path will be different on your machine. For a segment tree, the fix is tree = [0] * (4 * n).

Mixing inclusive and exclusive ends. In this module both ends of a range are included. A query (1, 3) covers indexes 1, 2 and 3. Python's own range(1, 3) and slices like a[1:3] stop before the end, so they cover only 1 and 2. Pick one rule and keep it. Mixing them gives an answer that is off by one item, and it is hard to spot.

Forgetting the colon. A small typing slip stops the program before it runs. If you leave out the colon at the end of an if, for or def line, Python reports a syntax error:

  File "example.py", line 1
    for i in range(3)
                     ^
SyntaxError: expected ':'

The caret marks the place where the colon should go. Add the colon there and run again.

Using a segment tree when the data never changes and only sums are needed. A prefix list is simpler and gives an O(1) query. Choose the simplest tool that meets the need.

Reading the three methods side by side

It helps to put the three methods next to each other, with the same example in mind. Imagine a list of ten thousand prices. Customers ask about the total of ranges of prices. The shop also changes one price a minute.

With a plain loop, each customer question walks through up to ten thousand prices. With prefix sums, each question is one subtraction, but each price change means rewriting up to ten thousand prefix values. With a segment tree, each question visits about 2 log2(10000), which is roughly 27 nodes, and each price change rewrites about 14 nodes on one path. Neither kind of work is large, and neither grows quickly.

The segment tree is not always the best choice. It has more code, more memory and more places to make a mistake. It earns its place when both queries and updates are common, and the list is large enough that the loop is too slow.

Two small worked examples

First example: the list is [2, 4, 6, 8]. Build the tree. The root covers [0..3] and its sum is 20. The root's left child covers [0..1] with sum 6, and its right child covers [2..3] with sum 14. The leaves are 2, 4, 6 and 8. Now answer query(1, 2), which is the items at indexes 1 and 2. The root is partly covered, so look at its children. The left child [0..1] is partly covered, so look at its leaves. The leaf [0] is outside the range and adds nothing. The leaf [1] is inside and adds 4. The right child [2..3] is partly covered. Its leaf [2] is inside and adds 6. The leaf [3] is outside. The total is 4 + 6 = 10. The next lesson shows this search as code.

Second example: the list is [5, 5, 5] and you ask for the range [1..2]. The root covers [0..2], so it is partly covered. Its left child [0..1] is partly covered, and its right child [2..2] is fully covered. The fully covered child has sum 5, and the leaf [1] inside [0..1] adds 5 too. The total is 10. Notice that the search never adds index 0. It stopped at the first node whose whole segment was inside the range. That early stop is the reason the search is fast.

Edge cases to check first

Good code handles the smallest inputs before it handles the typical ones. Three small cases come up again and again with segment trees, and each one is cheap to test.

The first case is a list with one item. The tree then has only a root, and the root is also a leaf. The build goes straight to the if l == r: line and stores the item. A query over that one index returns the item, and an update replaces it. This case is worth testing because the code that splits a range never runs.

The second case is a query where l equals r. That is a range of one item. The search still works, but it may visit a long path before it finds the leaf. Check that the answer matches the item at that index, because this is the simplest way to catch an off-by-one error.

The third case is an empty list, with n equal to 0. Here the build goes wrong. The top call is build(1, 0, -1). Python's floor division computes (0 + -1) // 2 as -1, not 0. The left child then becomes build(2, 0, -1), which is the same kind of call again, so the function never reaches a leaf. Python stops it when the recursion limit is reached:

Traceback (most recent call last):
  File "build.py", line 8, in <module>
    build(1, 0, len(a) - 1)
    ~~~~~^^^^^^^^^^^^^^^^^^
  File "build.py", line 3, in build
    build(2 * node, l, mid)
    ~~~~~^^^^^^^^^^^^^^^^^^
  File "build.py", line 3, in build
    build(2 * node, l, mid)
    ~~~~~^^^^^^^^^^^^^^^^^^
  File "build.py", line 3, in build
    build(2 * node, l, mid)
    ~~~~~^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The file name in the first line depends on where you save the code. The last line is the error, and the repeated lines show the same call again and again. The fix is simple. Check for an empty list before the build and skip it, or refuse empty input with a clear message. Interviewers often ask about empty input, because the answer shows whether you think about boundaries.

A fourth case, less obvious, is a query that covers the whole list. The root is fully inside the range, so the search returns the stored total at once. That is the fastest possible query, and it is a good check that the root holds the right value.

Interview questions this lesson prepares you for

Interviewers use range queries to test whether you can choose a data structure and defend the choice. Here are the questions that come up most often, along with the answer a strong candidate gives.

"Why not prefix sums?" Prefix sums are the right answer when the data is fixed. The strong answer names the update cost. A change to item i rewrites every prefix value from i onward, which is O(n). If the interviewer adds that updates are frequent, the answer changes to a segment tree or a Fenwick tree.

"What is the time for one query and one update?" The answer is O(log n) for both, and the candidate should say why. The query visits a few nodes per level and there are about log2(n) levels. The update changes one leaf and recomputes one parent per level. Mention that the build is O(n), because interviewers often ask for the total cost of a build followed by many operations.

"How much memory does the tree use?" The answer is about 4n references when you use the simple list layout. A stronger candidate adds that a tree with exactly 2n slots is possible with a clever layout, and that the 4n size is the safe default. Do not claim 2n works for every n, because the program in this lesson shows it does not.

"What if the operation is not sum?" The answer is that the tree works for any operation that combines two answers into one, is associative (grouping does not change the result, so (a + b) + c equals a + (b + c)), and has a neutral value (a value that changes nothing, such as 0 for a sum). Minimum, maximum and greatest common divisor (gcd) all fit. Average does not fit directly. You can still store a sum and a count.

"Walk me through a query by hand." Describe the three cases: outside the range, fully inside the range, and partly inside. Then trace the path for a small example, as the worked example in this lesson does. Interviewers like candidates who can name the cases before they write any code.

Where range queries show up in real programs

Range queries are common in real software, even when the programmer does not see the tree. A game uses them to total the points of a team over a window of matches. A finance tool sums the transactions in a date range, with a new transaction added each second. A chart library computes the average of a window of a time series as the user drags a slider. A database engine uses similar structures for "sum of this column between these two keys".

In each case the data changes often enough that prefix sums would be too slow. The loop would be too slow as well, because the ranges are large and asked for often. The segment tree is a good middle path. The same idea also appears in image processing, where a two-dimensional version answers "sum of pixels in this rectangle", and in network monitoring, where it answers "total traffic in the last minute".

A cost comparison with real numbers

Big O notation hides the constants, so it helps to see actual counts. Suppose the list has one thousand items. A loop answers a query in up to 1000 additions. Prefix sums answer it in 1 subtraction, but an update may rewrite up to 1000 cells. A segment tree answers a query in a few dozen node visits and an update in about 10 steps, because log2(1000) is roughly 10.

Now make the list one million items. The loop does up to one million additions per query. The prefix update may rewrite a million cells. The segment tree still stays in the range of a few dozen steps, because log2(1000000) is about 20. The next lesson counts the visited nodes for a query over a list of one million items, whose range covers almost the whole list.

The growth is the point. Multiplying the list by 1000 multiplies the loop's work by 1000. It adds only about 10 steps to the segment tree's work. That difference is what makes the structure worth learning.

Debugging a tree before you query it

A segment tree is easy to get wrong in a small way that does not crash. The program runs, and the answers are just slightly off. A good habit is to check the tree before you trust any query. Print every node after the build, as the build program above does, and compare the printed sums by hand.

Use three checks. First, the root must equal the sum of the whole list. Second, every parent must equal the sum of its two children. Third, every leaf must equal its item. If any check fails, the bug is in the build. The most common build bug is a wrong child index, such as calling build(2 * node, mid + 1, r, depth + 1) where the second call should use 2 * node + 1. That bug makes two calls write to the same node, so the right half overwrites the left, and the root total is wrong too (it comes out as 11 instead of 36 for this list).

A second habit is to test the simplest query first. Ask for the range [0..0] and compare with the first item. Then ask for the whole range and compare with the total you computed by hand. Only then try a middle range. The simplest checks find most bugs in a minute.

Choosing between the three tools

When you meet a range problem, ask three questions in order. Does the data change between queries? If not, use prefix sums, because they are the simplest and fastest query. Does the operation fit a simple sum that can be reversed, such as subtraction? If yes, a Fenwick tree (introduced in lesson 4 of this module) is compact and fast. Does the operation need minimum, maximum, gcd or a range assignment? Then use a segment tree.

This order keeps the design simple. Beginners often reach for the most powerful tool first. A segment tree that answers sums on a list that never changes is correct, but it is more code than the problem needs. A good engineer picks the smallest tool that meets the requirement, and says why when asked.

Practice

1. Draw the segment tree for [2, 4, 6, 8] with the sum in each node. Then write the node number of each leaf if the root is node 1.

Show the answer

The root [0..3] holds 20. Its children are [0..1] (sum 6, node 2) and [2..3] (sum 14, node 3). The leaves are [0] (node 4), [1] (node 5), [2] (node 6) and [3] (node 7). The leaves hold 2, 4, 6 and 8 in that order. The middle of [0..3] is (0 + 3) // 2 = 1, so the left child ends at index 1.

2. For [2, 4, 6, 8], use prefix sums to find the sum of indexes 1 to 2. Show the two prefix values you subtract.

Show the answer

The prefix list is [0, 2, 6, 12, 20]. The sum from index 1 to 2 is prefix[3] - prefix[1] = 12 - 2 = 10. This matches 4 + 6.

3. Explain in one sentence why a segment tree can also answer "what is the smallest value in a range?" Name the one change you would make to the code.

Show the answer

Each node can store the smallest value of its segment, and a parent stores the smaller of its two children. The only code change is to replace the addition with min in the build, the update and the query, and to use float("inf") instead of 0 for "no overlap".

4. In a tree stored in a list, is node 6 the left or the right child of node 3? Then give the slot numbers of the children of node 6.

Show the answer

Node 6 is the left child of node 3, because 2 * 3 = 6 and the right child is 2 * 3 + 1 = 7. The children of node 6 are slots 12 (2 * 6) and 13 (2 * 6 + 1).

5. Using the prefix list from the second program (before is [0, 1, 4, 9, 16, 25, 36]), predict how many prefix cells change if the item at index 0 becomes 5. Then check your answer by changing a[0] to 5 in the program and running it again.

Show the answer

The new list is [5, 3, 5, 7, 9, 11], so the new prefix list is [0, 5, 8, 13, 20, 29, 40]. Every cell from index 1 to index 6 changed, so the program prints 6. Only prefix[0], which is always 0, stays the same.

6. For a tree over 3 items, the largest slot used is 5 (from the program output). Explain why 2 times 3 slots, which is 6, would still be enough in this case, and why it is not enough for 6 items.

Show the answer

For 3 items the largest slot is 5, so slots 0 to 5 are needed and a list of length 6 holds them. For 6 items the largest slot is 13, which needs length 14. The list of length 2n = 12 only holds slots 0 to 11, so slot 13 is out of range. The size 2n works only by luck for small n.

7. For the segment [4..9], compute mid. Then give the ranges of the left child and the right child.

Show the answer

mid = (4 + 9) // 2 = 13 // 2, which is 6. The left child covers [4..6] and the right child covers [7..9]. Index 6 belongs to the left child only, and index 7 is the first index of the right child.

8. Write the Python expression that gives the sum of the items from l to r when prefix holds the running totals as in the first program. Then explain why the + 1 is needed.

Show the answer

The expression is prefix[r + 1] - prefix[l]. The prefix value at position i already covers the first i items, so the item at index r is included only once you move to r + 1. Without the + 1, the item at index r would be left out of the sum.

9. A tree over 4 items has leaves for each item and internal nodes above them. How many nodes does the tree have in total? Explain your count with the tree shape from this lesson.

Show the answer

It has 7 nodes. Four leaves hold the single items. Two nodes sit above them, one for each half, and the root is the last node. That is 4 + 2 + 1 = 7. In general a tree over n items has exactly 2n - 1 nodes, whatever n is.

What you now know

• A plain loop answers a range query in O(n) time and updates in O(1).
• Prefix sums answer a range query in O(1) time with one subtraction, but one update can rewrite up to n prefix values.
• A segment tree stores the answer for many segments in a binary tree. Its queries and updates both cost O(log n).
• The root covers the whole list, the leaves cover single items, and every node splits its range at mid = (l + r) // 2.
• In a list, the children of slot i sit at 2 * i and 2 * i + 1. Allocate 4 * n slots to be safe.
• The build is a recursion that finishes the children before the parent, so it costs O(n) overall.

The next lesson writes the full query, which chooses between three cases at each node.