## Table of Contents

Segment TreeResourcesSolution - Dynamic Range Minimum QueriesSolution - Dynamic Range Sum QueriesBinary Indexed TreeResourcesSolution - Dynamic Range Sum Queries (With a BIT)Solution 1Solution 2Finding the $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeExample - Inversion CountingSolutionRange Sum ProblemsGeneralUSACO# Point Update Range Sum

Authors: Benjamin Qi, Dong Liu, Nathan Gong

Contributors: Andrew Wang, Pramana Saldin

Introduces Segment Tree, Binary Indexed Tree, and C++ Order Statistic Tree.

### Prerequisites

## Table of Contents

Segment TreeResourcesSolution - Dynamic Range Minimum QueriesSolution - Dynamic Range Sum QueriesBinary Indexed TreeResourcesSolution - Dynamic Range Sum Queries (With a BIT)Solution 1Solution 2Finding the $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeExample - Inversion CountingSolutionRange Sum ProblemsGeneralUSACOFocus Problem – try your best to solve this problem before continuing!

Most gold range query problems require you to support following tasks in $\mathcal{O}(\log N)$ time each on an array of size $N$:

- Update the element at a single position (point).
- Query the sum of some consecutive subarray.

Both **segment trees** and **binary indexed trees** can accomplish this.

## Segment Tree

Focus Problem – try your best to solve this problem before continuing!

A **segment tree** allows you to do point update and range query in
$\mathcal{O}(\log N)$ time each for **any** associative operation, not just
summation.

### Resources

### Pro Tip

You can skip more advanced applications such as **lazy propagation** for now.
They will be covered in platinum.

Resources | ||||
---|---|---|---|---|

CF EDU | basic operations, inversion counting | |||

CSA | Interactive updates. | |||

CPH | Same implementation as AICash below. | |||

CPC | See slides after union-find. Also introduces sqrt bucketing. | |||

cp-algo | "Advanced versions" are covered in Platinum. |

### Solution - Dynamic Range Minimum Queries

Resources | ||||
---|---|---|---|---|

CF | simple implementation | |||

Benq | based off above |

C++

#include <iostream>#include <cassert>#include <vector>#include <algorithm>using std::cout;using std::endl;using std::vector;/** A data structure that can answer point update & range minimum queries. */

Java

import java.io.*;import java.util.*;/** A data structure that can answer point update & range minimum queries. */public class MinSegmentTree {private final int[] segtree;private final int len;public MinSegmentTree(int len) {this.len = len;

Python

import sysclass SegmentTree:"""A data structure that can answer point update & range minimum queries."""def __init__(self, arr: list[int], n: int) -> None:self.arr = arrself.n = nself.tree = [0] * (2 * n)for ii in range(n):

### Solution - Dynamic Range Sum Queries

C++

Compared to the previous problem, all we need to change are `DEFAULT`

and
`comb`

.

#include <iostream>#include <cassert>#include <vector>using std::cout;using std::endl;using std::vector;template<class T>class SumSegmentTree {

Java

Compared to the previous problem, all we need to change is the way we aggregate
values (from `Math.min()`

to summation) and the data type we use to store the
query (from `int`

to `long`

).

import java.io.*;import java.util.*;public class SumSegmentTree {private final long[] segtree;private final int len;public SumSegmentTree(int len) {this.len = len;segtree = new long[len * 2];

Python

Compared to the previous problem, all we need to change is the way we aggregate
values (from `min()`

to '+'), and change the initial value (sum) to 0.

import sysclass SegmentTree:def __init__(self, arr: list[int], n: int) -> None:self.arr = arrself.n = nself.tree = [0] * (2 * n)for ii in range(n):self.tree[n + ii] = arr[ii]

## Binary Indexed Tree

The implementation is shorter than segment tree, but maybe more confusing at first glance.

### Resources

Resources | ||||
---|---|---|---|---|

CSA | interactive | |||

CPH | similar to above | |||

cp-algo | also similar to above | |||

TC |

### Solution - Dynamic Range Sum Queries (With a BIT)

C++

#### Solution 1

#include <iostream>#include <cassert>#include <vector>using std::cout;using std::endl;using std::vector;/*** Short for "binary indexed tree",

Python

import sysclass BIT:"""Short for "binary indexed tree",this data structure supports point update and range sumqueries like a segment tree."""def __init__(self, arr: list[int], n: int) -> None:self.tree = [0] * (n + 1)

#### Solution 2

Writing a BIT this way has the advantage of generalizing to multiple dimensions.

Resources | ||||
---|---|---|---|---|

CF | ||||

Benq | based off above |

C++

/*** Description: range sum queries and point updates for $D$ dimensions* Source: https://codeforces.com/blog/entry/64914* Verification: SPOJ matsum* Usage: \texttt{BIT<int,10,10>} gives 2D BIT* Time: O((\log N)^D)*/template <class T, int ...Ns> struct BIT {T val = 0; void upd(T v) { val += v; }

Java

import java.io.*;import java.util.*;/*** Short for "binary indexed tree",* this data structure supports point update and range sum* queries like a segement tree.* */public class BIT {private final long[] bit;

## $k$-th Element

Finding theSuppose that we want a data structure that supports all the operations as a
`set`

in C++ in addition to the following:

`order_of_key(x)`

: counts the number of elements in the set that are strictly less than`x`

.`find_by_order(k)`

: similar to`find`

, returns the iterator corresponding to the`k`

-th lowest element in the set (0-indexed).

### Order Statistic Tree

Luckily, such a built-in data structure already exists in C++.

Resources | ||||
---|---|---|---|---|

CF | ||||

CPH | brief overview with find_by_order and order_of_key | |||

Benq | code |

To use indexed sets locally, you need to install GCC.

### With a BIT

Assumes all updates are in the range $[1,N]$.

Resources | ||||
---|---|---|---|---|

CF | log N |

### With a Segment Tree

Covered in Platinum.

## Example - Inversion Counting

Focus Problem – try your best to solve this problem before continuing!

### Solution

Solution

## Range Sum Problems

### Coordinate Compression

If the coordinates are large (say, up to $10^9$), then you should apply coordinate compression before using a BIT or segment tree (though sparse segment trees do exist).

### General

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsPURS | |||

Kattis | Easy | ## Show TagsInversions, PURS | |||

CSES | Easy | ## Show TagsPURS | |||

CSES | Easy | ## Show TagsCoordinate Compress, PURS | |||

CSES | Easy | ## Show TagsCoordinate Compress, PURS | |||

CSES | Normal | ## Show TagsOffline, PURS |

### USACO

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Gold | Easy | ## Show TagsInversions, PURS | |||

Gold | Easy | ## Show TagsInversions, PURS | |||

Gold | Easy | ## Show TagsInversions, PURS | |||

Gold | Easy | ## Show TagsPURS | |||

Plat | Easy | ## Show TagsInversions, PURS | |||

Old Gold | Hard | ## Show TagsPURS |

A hint regarding Sleepy Cow Sort: There is only one correct output.

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!