Dynamic segment tree for huge ranges

Why this matters

The segment trees in the earlier lessons of this module use an array with about four slots for every position. That works when the positions are 0 to n minus 1, with n around 200000. Many real problems use positions that are much larger. A timestamp in seconds can reach 1000000000. A phone number, a file size or an account id can be just as large. An array with one slot per possible value needs about one billion slots, which is 8 GB for 8-byte values. Most of those slots would never be used.

A dynamic segment tree solves this. It starts with one root node that covers the whole value range, and it creates the other nodes only when an update walks through them. A node that no update has touched never exists. The tree stores only the part of the value range that is actually in use.

The rules are the same as in the earlier segment trees. Each node covers a range of values. The two children split that range in half. Each node stores one combined answer for its range. Only the storage changes.

Words you will need

• Node: one box in the tree. It holds a stored answer and two links to its children.
• Child link: a number that says which slot holds the left child or the right child. The value 0 means there is no child.
• Pool: a std::vector of nodes. The tree refers to a node by its position in the pool, not by a pointer.
• Null node: the node in slot 0. It stands for "no node here". Nothing is ever written into it.
• Value range: the smallest and largest value the tree accepts. In this lesson it is written lo and hi.
• Count: the stored answer used in the first examples. It is the number of stored values that fall inside a node's range.
• Lazy creation: making a node at the moment an update needs it, and not before.
• long long: a C++ integer type that holds numbers up to about 9.2 times 10 to the 18. Use it for values near 10 to the 9 and above.

The idea with a small example

Take a tiny value range from 0 to 7. The root covers [0, 7]. Its midpoint is 3, so the left child covers [0, 3] and the right child covers [4, 7].

Insert the value 5 into an empty tree. The root already exists. The value 5 is greater than 3, so the update goes right. The right child covers [4, 7] and does not exist yet, so it is created. Its midpoint is 5. The value 5 is at most 5, so the update goes left. The left child covers [4, 5] and is created. Its midpoint is 4. The value 5 is greater than 4, so the update goes right. The right child covers [5, 5], a single value, and is created. That is three new nodes.

Now insert the value 1. The root exists, and the value 1 is at most 3, so the update goes left. The left child covers [0, 3] and is created. The value 1 is at most 1, so it goes left to [0, 1], which is created. Then the value 1 is greater than 0, so it goes right to [1, 1], which is created. That is three more new nodes.

The picture after both inserts is this.

[0, 7]  root, count 2
├── [0, 3]  count 1
│   └── [0, 1]  count 1
│       └── [1, 1]  count 1
└── [4, 7]  count 1
    └── [4, 5]  count 1
        └── [5, 5]  count 1

Only the nodes on the two paths exist. The other nodes that a full tree would have, such as [2, 3] and [6, 7], were never created. Measured with the class from worked example 1 on this range, the pool holds 7 nodes after these two inserts. That count includes the root, and it does not include the null node. After one insert it holds 4 nodes.

The same pattern holds for a huge range. The range from 0 to 1000000000 has about 30 halvings from the root to a single value. So one insert creates at most 30 new nodes. The first insert into an empty tree of that range, measured with the same class, produces 31 nodes in use. The root plus 30 new nodes is 31.

The three operations

A dynamic segment tree needs three operations. Each one follows a single path or a few paths from the root, so each takes about 30 steps for a range of 10 to the 9 values.

Add walks from the root down to the value. At each node it adds the change to the node's count. If the child on the path does not exist, it creates the child first. The walk stops at a leaf, a node that covers one value.

Count asks how many stored values lie between two numbers a and b. If the node does not exist, the answer for its range is 0. If the node's range lies completely inside [a, b], the answer is the stored count. If the range lies completely outside, the answer is 0. Otherwise the query asks both children and adds their answers.

Kth finds the k-th smallest stored value. It starts at the root. It looks at the left child's count. If k is at most that count, the answer is in the left half, so the walk goes left. If not, it subtracts the left count from k and goes right. The walk ends at a single value, which is the answer.

A count query on the small tree

Use the tree from the small example, with the values 1 and 5 inserted, and ask for the count of values from 2 to 5.

The root covers [0, 7], which only partly overlaps [2, 5], so the query goes on to both children. The left child covers [0, 3]. It also overlaps only partly, so the query goes on to its children. The child [0, 1] lies completely outside [2, 5], because its largest value 1 is below 2. It returns 0 at once. The child [2, 3] does not exist in the tree, so it returns 0 too.

The right child covers [4, 7]. It overlaps partly, so the query goes on. Its left child [4, 5] lies completely inside [2, 5], so the query returns the stored count, which is 1 for the value 5. The right grandchild [6, 7] lies outside the query and does not exist, so it returns 0.

The total is 0 + 0 + 1 + 0 = 1. The query visited 7 nodes, and it stopped early at the two nodes that lie completely inside or outside the query. This pruning is why a query costs about two paths down the tree and not the whole tree.

Worked example 1: a multiset over values up to 1000000000

A multiset is a collection that can hold the same value more than once. This program keeps a multiset of values from 0 to 1000000000. It accepts four kinds of lines. A line + x adds the value x. A line - x removes one copy of x. A line ? a b prints how many stored values lie between a and b. A line k n prints the n-th smallest stored value.

The count of a value is stored as a change of +1 for an insert and -1 for a removal. Adding -1 at a value cancels one earlier +1 at that value, so the counts stay correct.

Input, one command per line, with the first line holding the number of commands:

13
+ 700
+ 5
+ 700
+ 123456789
+ 0
? 0 1000000000
k 1
k 2
k 3
k 4
k 5
k 6
? 5 3

Output from running the program with g++ 15.2 and -std=c++20 -Wall:

5
kth 1 = 0
kth 2 = 5
kth 3 = 700
kth 4 = 700
kth 5 = 123456789
kth 6 = -1
0
nodes in use: 71

Read the output line by line. The first line is the count of values between 0 and 1000000000. There are five stored values, so the answer is 5. The next six lines show the sorted order: 0, 5, 700, 700, 123456789. The value 700 appears twice because it was inserted twice. The request for the sixth value returns -1, because only five values are stored. The query ? 5 3 has a start that is larger than its end, so it returns 0.

The last line counts the nodes. It is 71 here, and this program does not remove nodes when their count drops to 0.

How the code works

The add function changes count at every node on the path, from the root to the leaf. The line nodes_[node].count += delta runs before the leaf check, so the root and every node on the way down all change. A node is created only when the path needs it. The line nodes_[node].left = child stores the new child's position in the pool.

The code uses positions in nodes_, not pointers, on purpose. The vector grows when a new node is pushed. When it grows, it may move every node to a new place in memory. A pointer would then point at the old place. A position still means the same node after the move. Mistake 1 below shows what goes wrong with a reference.

The count function returns 0 for two cases. The first is a missing node, which means no value was ever stored in that range. The second is a range that lies completely outside the query. The stored count is used only when the range lies completely inside the query. This is the same rule the segment trees of the earlier lessons use.

The kth function does the walk described in the last section. It needs the count of the left child. The code reads the left child's count only when the left child exists, because a missing child has a count of 0.

Worked example 2: the same code with values up to 10 to the 18

The code above works for any range, as long as the numbers fit in long long. Change the constructor call in main so the range is from 1 to 10 to the 18. Nothing else changes in the class.

DynamicCounts counts(1, 1000000000000000000LL);

The range now has about 60 halvings from the root to a leaf, so each insert creates about 60 nodes at most. The left bound is 1 instead of 0, so every value must be at least 1.

Input:

6
+ 1000000000000000000
+ 1
+ 999999999999999999
? 1 1000000000000000000
? 2 999999999999999998
k 2

Output:

3
0
kth 2 = 999999999999999999
nodes in use: 122

The first query counts all three stored values, so it prints 3. The second query asks for values from 2 up to 999999999999999998. None of the three values lies in that range, because the values are 1, 999999999999999999 and 10 to the 18. The second smallest value is 999999999999999999. The three inserts created 121 nodes, which is about 40 nodes per insert. The first insert alone created 59 new nodes. Later inserts share their top nodes with the earlier ones, so they create fewer.

The midpoint formula l + (r - l) / 2 is important at this size. Mistake 3 shows why.

Worked example 3: memory grows with the number of inserts

The range size does not decide the memory. The number of inserts does. This example keeps the same class and changes only main. It inserts pseudo-random values from 0 to 1000000000. A pseudo-random generator produces numbers that look random but come from a fixed formula. Because the seed is fixed, the numbers are the same on every run.

int main() {
    DynamicCounts counts(0, 1000000000LL);
    unsigned long long seed = 42;
    auto nextValue = [&seed]() {
        seed = (seed * 6364136223846793005ULL + 1442695040888963407ULL);
        return static_cast<long long>((seed >> 33) % 1000000000ULL);
    };
    int inserted = 0;
    for (int batch : {1000, 10000, 100000}) {
        while (inserted < batch) {
            counts.add(nextValue(), 1);
            inserted++;
        }
        cout << "inserted " << inserted << " values, nodes in use: " << counts.nodesInUse()
             << ", bytes: " << counts.nodesInUse() * sizeof(DynamicCounts::Node) << "\n";
    }
    return 0;
}

Output:

inserted 1000 values, nodes in use: 20962, bytes: 335392
inserted 10000 values, nodes in use: 177330, bytes: 2837280
inserted 100000 values, nodes in use: 1440984, bytes: 23055744

The node size is 16 bytes. The program prints sizeof of the node type, which is 16 on this build. The byte count in the output is the node count times 16. It leaves out the spare room that a vector keeps after it grows, so the real memory use can be somewhat higher.

Look at the nodes per insert. The first 1000 inserts create about 21 nodes each. The next 99000 inserts create about 14 each on average. The top levels of the tree are shared by almost every value, so each new value adds fewer new nodes once the top is built. Each value still needs its own path near the bottom, which is why the count keeps growing.

A rough upper bound follows from the depth. Practice exercise 5 works it out for 200000 inserts.

Common mistakes

Mistake 1: keeping a reference into the pool

The most common bug is to hold a reference to a node and then add a child. The pool grows when a child is added. When it grows, the old memory is freed, so the reference points at freed memory. Writing through it is undefined behaviour. In practice the program may crash, or it may appear to work until a later run.

This is the wrong pattern.

Node& cur = nodes[1];                // reference into the vector's buffer
nodes.push_back(Node{});             // may reallocate and free the old buffer
cur.left = static_cast<int>(nodes.size() - 1);   // writes through a freed reference

Compiled with -fsanitize=address, the address sanitizer stops the program and prints this report. The first lines are these.

=================================================================
==810122==ERROR: AddressSanitizer: heap-use-after-free on address 0x7c2943de0058 at pc 0x650636424688 bp 0x7ffd5045f8f0 sp 0x7ffd5045f8e0
WRITE of size 4 at 0x7c2943de0058 thread T0
    #0 0x650636424687 in main /path/to/l12_bad_ref.cpp:16

The address sanitizer is a checking mode built into g++. The line number refers to the sample file that holds the bad pattern, not to this lesson. The directory part of the path is shortened here. The addresses and process id change on every run. The fix is the code in the class above. It stores the index, and it reads nodes_[node] again after each push.

Mistake 2: values outside the range

The tree has no check on its inputs. If a value lies outside [lo, hi], the add walk always goes to one edge. A value below lo goes left at every level and ends at the leftmost leaf. A value above hi goes right and ends at the rightmost leaf. The program does not report an error. The wrong value is stored at an edge, and later queries may count it.

The next input uses a range from 0 to 1000000000 and inserts the value -1, which is below the range.

3
+ -1
? 0 0
? -5 0

Output:

1
1
nodes in use: 31

The query ? 0 0 should print 0, because -1 is not between 0 and 0. The program prints 1. The second query is correct, because -1 is between -5 and 0. The fix is to check the value before the call to add, and to throw an error or skip the line when the value is outside the range.

Mistake 3: using int for the bounds

The bounds of a huge range do not fit in int. The largest int is 2147483647. A bound such as 10 to the 18 needs long long. The g++ compiler reports this mistake with a warning when it sees the number written out.

int hi = 1000000000000000000LL;

Real output from g++ -std=c++20 -Wall:

l12_int.cpp: In function 'int main()':
l12_int.cpp:3:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]

A value that is computed at run time gives no warning, so read the types of every bound.

The midpoint has the same kind of problem. The formula (l + r) / 2 adds two values before it divides. With two int bounds near 2000000000, the sum is larger than the largest int. In a test on this machine the result was -147483648 instead of 2000000000. Signed overflow is undefined behaviour in C++, so the result can be anything. The formula l + (r - l) / 2 never adds two large numbers, so it is safe. The class uses it.

Mistake 4: calling a function with the wrong arguments

The class has two functions named add. The public one takes two arguments, the value and the change. The private one takes five and is used only inside the class. Calling the public one with one argument gives this error from g++.

l12_err.cpp:85:15: error: no matching function for call to 'DynamicCounts::add(int)'
   85 |     counts.add(3);
      |     ~~~~~~~~~~^~~
l12_err.cpp:85:15: note: there are 2 candidates
l12_err.cpp:19:10: note: candidate 1: 'void DynamicCounts::add(long long int, long long int)'
   19 |     void add(long long value, long long delta) { add(1, lo_, hi_, value, delta); }
l12_err.cpp:55:10: note: candidate 2: 'void DynamicCounts::add(int, long long int, long long int, long long int, long long int)'

The output is shortened by removing the source lines that g++ prints under the candidate notes.

The message lists both candidates and how many arguments each one takes. The fix is to pass the change as well, as in counts.add(3, 1).

Practice

1. How many nodes are in use after the first insert into an empty tree for the range from 0 to 1000000000? Count the root.

Show the answer

The root exists before the insert, so the insert creates 30 new nodes. With the root, that makes 31 nodes in use. Measured with the class from worked example 1, one insert into this range leaves 31 nodes in use.

2. The program returns 0 for the query ? 5 3. Which line of count makes that happen, and why does it not need a special case?

Show the answer

The line if (node == 0 || b < l || r < a) return 0; does it. When a is greater than b, no value can be at least a and at most b. Every node then either lies outside the query, which the test b < l || r < a catches, or fails the test for a node that lies fully inside, so the recursion adds up 0 everywhere.

3. Write the midpoint formula for int bounds that never overflows, and explain in one sentence why it is safe.

Show the answer

Use int mid = l + (r - l) / 2;. The difference r - l is never larger than the range itself, and adding it to l gives a value that is still inside the range, so no intermediate result is too large for int.

4. The program never removes a node when its count falls to 0. Give one reason this is acceptable and one reason it can become a problem.

Show the answer

It is acceptable because a node with count 0 adds nothing to any answer, so the results stay correct. It can become a problem when a program inserts and removes many different values, because the pool keeps growing even when few values are stored.

5. A program makes 200000 inserts into a range from 0 to 10 to the 9. Estimate the most memory the pool can need, in megabytes, using 16 bytes per node and at most 30 new nodes per insert.

Show the answer

The pool holds at most 200000 times 30, which is 6000000 nodes. Each node takes 16 bytes, so the total is 96000000 bytes, about 96 MB. This is an upper bound, because the top levels are shared, as worked example 3 shows.

Summary

• A dynamic segment tree creates a node only when an update walks through it, so the range can be as large as the long long type allows.
• Nodes refer to their children by index into a vector, and index 0 means "no child".
• Add, count and kth each walk down the tree along about 30 or 60 levels for ranges of 10 to the 9 or 10 to the 18.
• The pool size depends on the number of inserts, not on the size of the range.
• Compute the midpoint as l + (r - l) / 2 and keep the bounds in long long.
• Check that every value lies inside the range before inserting it.