Range queries and why we need a tree

Why it matters

Many programs ask the same kind of question again and again. "What were the total sales from day 10 to day 40?" "What was the lowest temperature between Monday and Friday?" Each question looks at a slice of a list. If the list is short and the questions are few, a simple loop is fine. If the list has a million items, the questions arrive every second, and the list changes between questions, you need a better structure. That structure is the segment tree, and this module builds it step by step.

This first lesson does three things. It defines the problem in plain words. It shows the two simple methods that most beginners reach for first. And it shows exactly where each method breaks, because that break is the reason segment trees exist.

Start with the array

Before any clever structure, you need the basic tool: the array. An array is a row of boxes in memory. Each box holds one value, and all the boxes hold values of the same type. Each box has a number called its index. In C++ indexes start at 0. The first box is index 0, the second is index 1, and so on. Each box is also called an element.

In C++ you usually write an array as a vector. A vector is a resizable array from the standard library. The line vector<long long> a(5); makes five boxes, each holding 0 at the start. The line a[2] = 7; puts 7 into index 2. The expression a[2] reads that value back.

Think of a row of lockers in a school corridor. Each locker has a number on its door, which is its index. You can open locker 2, put something in it, or look inside. The lockers sit side by side in one line, so the program can jump straight to locker 4 by counting from the start. Nothing has to be searched. That is why reading and writing one element of an array is fast.

Each long long takes 8 bytes on a typical computer, so five of them take 40 bytes in one block of memory. An int usually takes 4 bytes. The exact size depends on the platform, and you can check it yourself with sizeof(int). The size matters later, when we ask whether a sum fits in an int.

What a range is

A range is a run of neighbouring elements. We write a range as [l, r], read "from l to r", and both ends are included. In the array {2, 4, 1, 7, 3}, the range [1, 3] is the elements at indexes 1, 2 and 3. Those values are 4, 1 and 7. The length of a range is r - l + 1, so [1, 3] has length 3.

We include both ends because that matches how people talk. "Days 10 to 40" includes day 40. Some C++ library functions use a different style called a half-open range, [l, r), where the right end is not included. Either style is fine. What matters is that you pick one, write it down, and stick to it. Mixing the two styles in the same program is the most common cause of off-by-one errors in this topic, and you will see an example of that mistake later in this lesson.

A range with l equal to r holds exactly one element. A range with l greater than r holds nothing, and the questions in this module never ask for one. When you write the code, make sure l <= r holds before you use the range.

Three questions a range can ask

This module cares about three questions that a range can ask:

• The sum: add up all the values in the range.
• The minimum: find the smallest value in the range.
• The maximum: find the largest value in the range.

Each question takes many values and combines them into one answer. Computer scientists say that the combining operation is associative. That is a fancy word with a simple meaning: the grouping does not change the result. The sum of 4, 1 and 7 is the same whether you add 4 and 1 first or 1 and 7 first. The minimum is the same too. Keep this idea in mind, because a segment tree only works for operations with this property.

A segment tree also needs a neutral value. That is a value that changes nothing when you combine it with a real answer. For sums the neutral value is 0, because adding 0 changes nothing. For minimums it is a very large number, because the smaller of a real value and a very large number is always the real value. For maximums it is a very small number. You will meet these values again in the next lesson, where they decide what a query returns when a piece of the tree lies outside the range.

An everyday picture

Imagine a shop that writes each day's sales in a notebook, one line per day, in order. The owner does two kinds of work with that notebook.

First, the owner asks questions: "How much did we sell between day 10 and day 40?" Questions come often, sometimes dozens in a morning. Second, the owner fixes mistakes: "On day 17 the till said 300, but the real figure was 30." Corrections are rarer, but they happen while the questions keep coming.

There are two obvious ways to answer the questions. The first is to add up the lines each time you are asked. That is slow when the notebook is long, but a correction is instant: you just cross out one number and write the new one. The second is to keep a running total table, so that each answer is a quick subtraction. That is fast to answer, but a correction forces you to rewrite every running total after the mistake. The rest of this lesson measures exactly how much work each method does, so you can see the trade-off with numbers instead of guessing.

Method 1: the plain loop

The simplest method is to loop over the range and add the values as you go. In C++ the core of it looks like this:

long long total = 0;
for (int i = l; i <= r; i++) total += a[i];

The loop runs once for each element in the range. A query over a range of length 3 does 3 steps. A query over the whole array of length n does n steps. We write that cost as O(n), read "order n", which means the work grows in step with n. Big-O notation describes how the work grows as the input grows. It ignores constant factors, so O(n) covers both "n steps" and "2n steps".

An update is different. To change one element, you just write the new value into its box: a[i] = v;. That is one step no matter how long the array is. We write that cost as O(1), read "order one", which means constant time.

So the plain loop gives you this trade: queries cost O(n) and updates cost O(1). Let us see the loop at work. The program below answers minimum queries and reports how many steps each query took. Type the input into the Input box, one line at a time, before you press Run.

Input, one item per line:

5
4 9 2 7 5
3
0 2
1 4
3 3

Expected output:

min 2 in 3 steps
min 2 in 4 steps
min 7 in 1 steps

Read the output line by line. The first query asks for indexes 0 to 2, which hold 4, 9 and 2. The smallest is 2, and the loop took 3 steps because the range has 3 elements. The second query asks for indexes 1 to 4, which hold 9, 2, 7 and 5. The minimum is still 2, found in 4 steps. The third query asks for index 3 alone, which holds 7. One step, answer 7.

Notice the pattern in the step counts. Each count equals the length of its range. The program never skips anything, so it never gets faster. If the array has a million values and the program gets a million queries over long ranges, the loop does on the order of a trillion steps. A modern computer does a few billion simple steps per second, so that run would take minutes or hours. We need something that does not walk every element on every query.

Method 2: prefix sums

The second method changes what we store. Instead of the values themselves, we store running totals. Define an array pre where pre[i] is the sum of the first i elements. That is, pre[i] equals a[0] + a[1] + ... + a[i-1]. The table has one more cell than the array, so pre[0] is 0: the sum of no elements at all.

Here is the table for {2, 4, 1, 7, 3}:

Each cell is the previous cell plus the next element. pre[1] is 0 + 2 = 2. pre[2] is 2 + 4 = 6. pre[3] is 6 + 1 = 7. pre[4] is 7 + 7 = 14. pre[5] is 14 + 3 = 17.

Now the key step. The sum of the range [l, r] is the total up to the end of the range, minus the total up to just before the range starts. The total up to the end of [l, r] is pre[r+1], because pre[r+1] covers indexes 0 through r. The total up to just before l is pre[l]. So the answer is:

sum of a[l..r] = pre[r+1] - pre[l]

Check it with the range [1, 3], which should give 4 + 1 + 7 = 12. The formula gives pre[4] - pre[1], which is 14 - 2 = 12. The range [0, 4] gives pre[5] - pre[0] = 17 - 0 = 17, which is the whole array.

The cost has changed completely. Building the table takes one pass over the array, so O(n) once. After that, each query is two lookups and one subtraction, so O(1) per query. This is the fastest possible answer for a sum over a fixed array. Here is a complete program. It reads the array and then the queries, and it builds the table once.

Input, one item per line:

5
2 4 1 7 3
3
1 3
0 4
2 2

Expected output:

12
17
1

The first answer is 12, the sum of indexes 1 to 3. The second is 17, the whole array. The third is 1, the single element at index 2. Each query did two array reads and one subtraction. The loop version of the same program would have needed 3, 5 and 1 additions, so for these tiny numbers the difference is small. For a long array with many queries, the difference is enormous.

What happens inside the computer

When you write pre[r + 1], the program does not search for the cell. The vector stores its boxes one after another in a single block of memory. The address of cell i is the start of the block plus i times the size of one cell. For long long cells, that is 8 bytes per cell. The processor computes the address with one multiplication and one addition, then reads the value. That is why O(1) lookups are real and not just a claim on paper.

The + 1 in pre[r + 1] exists because pre is shifted one cell to the right. Cell 0 is the sum of nothing, and cell i is the sum of the first i elements. Without the shift, the first element would have no cell that covers it alone, and the formula would need a special case for l = 0. The shift removes that special case. The price is one extra cell, which costs 8 bytes.

The loop that builds pre reads each element once and writes each cell once. It uses one loop, not nested loops, so the build is a single pass of n steps.

The trouble with updates

Now the owner's correction. Suppose the second element changes from 1 to 10, so the array becomes {2, 4, 10, 7, 3}. The program must handle that change and then keep answering queries. The simplest correct approach is to rebuild the table after each change, and the program below does exactly that. It also reads a list of commands from the Input box. A line starting with q asks a query. A line starting with u updates one element.

Input, one item per line:

5
2 4 1 7 3
4
q 1 3
u 2 10
q 1 3
q 0 4

Expected output:

12
21
26

Trace it step by step. The first q 1 3 runs on the original array and gives 4 + 1 + 7 = 12. Then u 2 10 sets index 2 to 10, so the array is now {2, 4, 10, 7, 3}. The program rebuilds the table, which is the expensive part. The next q 1 3 gives 4 + 10 + 7 = 21. The last query q 0 4 gives 2 + 4 + 10 + 7 + 3 = 26. Every answer is correct, and the queries stayed fast. The updates were not.

Why did the update cost so much? Setting one element changed the total of every prefix that covers it. In the table above, pre[3], pre[4] and pre[5] all contain the old value of a[2]. The picture below shows the table before and after the change. Three cells must be rewritten, and in general the rewrite can touch every cell after the changed index. The rebuild loop does exactly that, so an update costs O(n).

A table of prefix sums before and after setting a[2] from 1 to 10. Cells 3, 4 and 5 change.

So we now have a clear trade-off. Plain loops give O(n) queries and O(1) updates. Prefix sums give O(1) queries and O(n) updates. A workload with many queries and no updates suits prefix sums. A workload with many updates and few queries suits the plain loop. A workload with both, at scale, needs a different structure. The segment tree is built to balance the two, giving O(log n) for both. Keep that target in mind: the rest of the module is about reaching it.

Why prefix sums cannot handle the minimum

The subtraction trick depends on a property that sums have and minimums do not. For sums, you can take away the left part by subtraction: the total up to r minus the total up to l - 1 leaves exactly the middle. Mathematicians call a subtraction an inverse of addition. A sum has an inverse, so the trick works.

A minimum has no inverse. If you know the smallest value among the first r+1 elements and the smallest among the first l elements, you cannot work out the smallest among the middle elements. Some values in the middle could be much bigger than the total minimum, and the prefix minimums hide them.

Here is a concrete case. Take the array {4, 9, 2, 7, 5}. The prefix minimums are the smallest value among the first i elements. Cell 0 is "no elements", so we give it a very large number. The table is:

Now try the same formula for the range [3, 4], whose values are 7 and 5. The answer should be 5. The formula would be the prefix minimum at r+1 minus the prefix minimum at l, which is pre[5] - pre[3] = 2 - 2 = 0. The answer 0 is wrong, and no choice of subtraction fixes it, because the minimum of the first five elements (2) came from the element at index 2, which is not in the range at all. Prefix minimums simply cannot answer range minimums. You need a structure that combines the values inside the range directly, and that is what the segment tree does.

Overflow: the sum can outgrow the number type

There is one more trap, and it has nothing to do with the structure. A type has a largest value it can hold. An int in C++ usually holds values from -2147483648 to 2147483647. A sum of several large values can pass that limit even though each value fits easily.

The program below adds three values of 2000000000. Each value fits in an int, but the total is 6000000000, which does not. So the program stores the values and the total in long long, which holds numbers up to about 9.2 quintillion on most systems.

Input, one item per line:

3
2000000000 2000000000 2000000000

Expected output:

sum 6000000000

If you change the program to use int for total and vector<int> for the values, the result is wrong. In C++, a signed int that overflows is undefined behaviour. That means the language does not promise any result, so the program may print a wrong number, or the compiler may assume the overflow never happens and optimise the code in a surprising way. The safe habit is to pick long long whenever a sum could be large. A prefix table built from a million values of size one million reaches a total near 10^12, which is far past int.

What the answers depend on

Before moving on, look at what our two methods depend on. The loop depends only on the values in the range, so it works for any operation and any array. Prefix sums depend on subtraction, so they only work for sums and similar operations that have an inverse. A segment tree depends only on the operation being associative and having a neutral value. That is a much weaker requirement, and it is why the segment tree can handle minimums and maximums, which prefix sums cannot.

Reading a problem before you choose a method

Most of the work in choosing a method happens before any code is written. When you meet a problem that asks about ranges, ask yourself four questions, in this order. What is combined: a sum, a minimum, or something else? How many queries come, and how many updates? How big is the array? Does any operation have to undo a value, that is, does it need subtraction or some other inverse?

The answers point to a method. A small array with a few questions points to the loop, because it is simple and fast enough. A fixed array with many sum queries points to prefix sums. A changing array with minimum or maximum queries points to a segment tree. A changing array with sum queries points to a Fenwick tree or a sum segment tree. Getting this step right matters more than typing speed, because the wrong structure can be fast for the wrong reasons and then fail when the data grows.

Take a concrete example. A website counts visits per hour for a year, which is 8760 values, and a report asks for the total visits in any window of hours. The data is written once per hour and read by many reports. The array changes only at the end of each hour, and the windows are sums. Prefix sums fit the pattern well: each hour adds one new value, and that is an update at the end of the array, which for prefix sums is a single new cell, not a rewrite of every cell. The lesson is that the cost of an update depends on where it lands. A change at the end of a prefix table is cheap. A change at the start is expensive.

Now change the report. Analysts also correct old hours, because a sensor was wrong. Each correction can land anywhere in the year. That changes the picture: corrections at the start cost almost a full rebuild, and the reports keep coming. This is the moment to reach for a segment tree or a Fenwick tree, because both keep corrections and reports at O(log n).

A cost table for realistic sizes

Big-O notation can feel abstract, so it helps to put real numbers in front of it. Take an array of one million values and one million operations, a mix of queries and updates. A rough guide to the work is the number of basic steps each method needs. The numbers below are approximate, and they ignore constant factors, but they show the scale.

The segment tree column uses log2 of one million, which is about 20. Twenty steps per operation is a small number even when the array is large. The plain loop and prefix sums each have one column that is fine and one that is catastrophic. The segment tree has no catastrophic column. A computer doing a few hundred million simple steps per second finishes 2 times 10^7 steps in a fraction of a second, and it would take many minutes for 10^12 steps.

This is why the course spends so much time on the segment tree. It is not that the loop is wrong. The loop is correct every time. It is that the loop's total grows with the product of the number of queries and the length of the ranges, while the segment tree's total grows with the sum of the logs. For small inputs both finish instantly. For the inputs that real systems see, only one of them finishes in time.

Testing a structure before you trust it

Every method in this lesson can be checked against the plain loop. The loop is slow, but it is simple enough to be obviously correct, so it makes a good reference. A standard habit is to write the loop first, then write the fast method, then test the fast method on many random inputs and compare the answers. If they ever disagree, the fast method has a bug. The loop does not.

For small arrays you can check every range. For an array of length n there are n times (n + 1) divided by 2 ranges, so an array of 10 values has 55 ranges, which is a complete test in a fraction of a second. For larger arrays, pick random ranges and random updates, and use a fixed seed so that a failing test can be repeated. The later lessons show the exact code for this kind of check, and you will use it in the module assignment.

Common mistakes

These are the mistakes that show up most often in this topic. Each one has a real message or a real symptom, so you can recognise it.

Forgetting a header. The code uses INT_MAX but the program has no #include <climits>. g++ stops with this message:

error: 'INT_MAX' was not declared in this scope

The fix is to add #include <climits> at the top. The same happens with vector if you forget #include <vector>, and g++ says error: 'vector' was not declared in this scope.

Off-by-one in the formula. Writing pre[r] - pre[l] instead of pre[r + 1] - pre[l] compiles without any warning, but the answer is wrong. For the query [1, 3] on {2, 4, 1, 7, 3}, the wrong formula gives pre[3] - pre[1] = 7 - 2 = 5. That is the sum of indexes 1 and 2 only, so it leaves out the last element, 7. Always check the formula with one small case by hand.

Using the wrong neutral value. A minimum that starts at 0 gives wrong answers when all values are positive, because 0 is always smaller than the real values. Start minimums at INT_MAX or at a very large long long instead.

Reading past the end. If r is 5 for an array of length 5, the index 5 does not exist. C++ does not check that for a vector in most builds, so the program may print a garbage number or crash. Some builds of g++ check the index and stop with a message. This one came from a g++ 15 build:

Assertion '__n < this->size()' failed.

Treat that message as a sign that your range is outside the array.

Mixing int and long long. A sum can be correct in every step but still wrong at the end if an intermediate int overflows. Use long long for all totals.

Debugging walkthrough: a wrong answer with no error

Here is a bug you will meet in practice. A learner writes prefix sums and gets the wrong answer for one query. The program compiles and runs without any message. The learner wants to find the cause without guessing.

The array is {2, 4, 1, 7, 3}, and the query is [1, 3]. The correct answer is 12. The program prints 5. The learner starts by printing the table, which is the first place to look:

pre = 0 2 6 7 14 17

The table is right. Now the learner checks the formula step by step. The query needs pre[r+1] - pre[l], with l = 1 and r = 3. The code says pre[r] - pre[l], which is pre[3] - pre[1] = 7 - 2 = 5. Five is the sum of indexes 1 and 2, which is 4 + 1. The last element, 7, is missing. The fix is to use r + 1, and the output becomes 12.

The lesson from this walkthrough is a method. Check the data structure first, because it is easy to inspect. Then check the formula with the smallest range you can, by hand. A mistake in an off-by-one index almost always shows up as a sum that is missing one end.

Variations and edge cases

Interviewers like to check the edge cases, so here are the ones that matter for this lesson.

A range of length 1 (l equal to r) must work. With prefix sums it is pre[l+1] - pre[l], which is a[l]. With the loop it is one step.

A range covering the whole array (l = 0 and r = n - 1) must work. The formula gives pre[n] - pre[0], which is the full total.

An array of length 0 is a special case. The table has one cell, pre[0] = 0. Any range query on an empty array is invalid, so you should not ask one. Check your inputs before you call the query.

Negative values are allowed for sums. The formula does not care about the sign of the values, and long long handles negative totals just as well as positive ones.

Equal values are allowed too. A minimum over a range of equal values returns that value, however long the range.

Comparing the options

The table below puts the three methods side by side. Use it as a quick reference when you choose a tool.

The loop is the right answer when the array is short or the queries are rare. Prefix sums are the right answer when the array is fixed and only sums are asked. The segment tree is the right answer when the array changes, the questions include minimums or maximums, and the sizes are large. Being able to say which case you are in is the skill an interviewer is looking for.

In an interview you might hear: "We have an array of 100000 values. The values change and we ask range sums many times." A strong answer names the operations first. Updates and queries both happen, so prefix sums are out, because each update costs O(n). The loop is out, because 100000 queries of length 100000 is 10^10 steps. A Fenwick tree or a segment tree gives O(log n) for both, so that is the answer, and you explain why.

In real programs these questions come up in dashboards that show the total of the last 30 days, in stock systems that track counts over a range of bins, and in games that ask for the sum of scores in a range of levels. The same structures appear anywhere a list of numbers is both read and changed.

Diagram: a range query picks a slice

The figure below shows the idea of a range query. The highlighted cells are the slice, and only those cells affect the answer.

An array of five values with indexes 1 to 3 highlighted, showing that query(1, 3) sums only those cells.

Practice

1. For {3, 1, 4, 1, 5}, write the prefix table pre by hand. Then use it to compute the sum of indexes 2 to 4. Check your answer by adding the three values directly.
2. Which structure suits 100 queries on a fixed array with no updates? Which suits 100000 mixed queries and updates? Give one reason for each choice.
3. Explain in one sentence why prefix sums cannot answer range-minimum queries. Use the word "inverse" in your answer.
4. The table pre for {5, 5, 5} is 0 5 10 15. What does pre[3] - pre[1] give, and which range does it describe?
5. Write the formula for the sum of a[l..r] with a prefix table, and say why it needs r + 1.
6. A plain loop answers a query over indexes 0 to 999 in how many steps? How many steps does an update to one element take?
7. Change the first runnable program so it prints the sum of each query instead of the minimum. What changes in the loop body, and what stays the same?
8. A learner's program prints pre[r] - pre[l] for every query. Give one input where this gives the right answer and one where it gives a wrong answer.
9. Why does the program with int values fail for three values of 2000000000 even though each value fits? Name the type that fixes it.
10. Design a test: a small array and three queries that together catch an off-by-one error in either direction. Write the expected answers.

What you now know

• A range [l, r] covers indexes l through r, both included.
• A plain loop answers a query in O(n) and an update in O(1).
• Prefix sums answer a sum in O(1) after an O(n) build, but an update costs O(n).
• The formula pre[r+1] - pre[l] depends on subtraction, which minimums do not have.
• Use long long for totals, and start minimums at a very large value.
• A segment tree is needed when updates and queries both happen often and the operation has no inverse.