What can Segment Tree do?

Segment Tree is a useful data structure that can solve problems like RMQ in $$$O(n)$$$ build tree and $$$O(\log(n))$$$ for each query or update.

What can it query?

• sum

• maxinum / minium

• gcd / lcm

• other thing that can be push up

How to use Segment Tree?

Lets use segment Tree to query the sum of an array.

Build Tree

Lets look at the example, the tree is just like many segments!

It's easy to find that the number on the bottom is the sum of the two numbers on it.

The $$$l$$$ and $$$r$$$ note the left endpoint and the right endpoint of this segment.

The next step is the give each segment an idx to mark their position. The purple letters on top of the segments are the idxs.

It's not beautiful to put big segments in the bottom, so we can reverse it like this:

We always use $$$ls$$$ to represent the left son of a segment and use $$$rs$$$ to represent its right son. We can find that $$$ls = pos \times 2$$$ and $$$rs = ls + 1$$$ ($$$pos$$$ is the id of the father segment). So we have:

#define ls (o << 1)
#define rs (ls | 1)

Note that there are some segments which have many idxs. This operation can help us to find the $$$ls$$$ and $$$rs$$$ quickly, but it will waste some memery. Scientists calculation shows that the total memery we use will not exceed four times the length of the interval.

code of build tree:

void build(int o, int l, int r)
{
	if (l == r)
	{
		sum[o] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
//get the middle and cut the segment into two
	build(ls, l, mid);
	build(rs, mid + 1, r);
//build the left son and the right son
	sum[o] = sum[ls] + sum[rs];
}

Query without update

Let look at the example. If I want to query the sum from $$$a_3$$$ to $$$a_9$$$, we don't have to add them up, we can add sum[l = 3, r = 4], sum[l = 5, r = 8] and sum[l = 9, r = 9]. The time complexity is only $$$O(\log(n))$$$.

Prove: we will add only a number in a layer, and there are at most $$$\log(n)$$$ layers, so the number of the operation will not exceed $$$O(\log(n))$$$.

That read the code together:

ll query(int o, int l, int r)
{
	if (ql <= l && r <= qr) return sum[o];
	int mid = (l + r) >> 1;
	ll s = 0;
	push_down(o, l, r);
//push_down is used to update, I will explain it next.
	if (ql <= mid) s += query(ls, l, mid);
	if (mid < qr) s += query(rs, mid + 1, r);
	return s;
}

In the code, I use $$$ql$$$ to represent the left endpoint of the query, and use $$$qr$$$ to represent the right endpoint.

if (ql <= l && r <= qr) return sum[o]; This means if our query contains the segment, add it up.

if (ql <= mid) s += query(ls, l, mid);
if (mid < qr) s += query(rs, mid + 1, r);

If a part of the query is in the left son, visit it. If a part of the query is in the right son, visit it.

Update

I will introduce it in my next aritical.