## Table of Contents

Segment TreeResourcesSolution - Dynamic Range Minimum QueriesSolution - Dynamic Range Sum QueriesBinary Indexed TreeResourcesSolution - Dynamic Range Sum Queries (With a BIT)Finding 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

Segment Tree, Binary Indexed Tree, and Order Statistic Tree (in C++).

### Prerequisites

## Table of Contents

Segment TreeResourcesSolution - Dynamic Range Minimum QueriesSolution - Dynamic Range Sum QueriesBinary Indexed TreeResourcesSolution - Dynamic Range Sum Queries (With a BIT)Finding the $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeExample - Inversion CountingSolutionRange Sum ProblemsGeneralUSACOMost 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 | |||

KACTL | similar to above |

C++

#include <algorithm>#include <iostream>#include <limits>#include <vector>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

class MinSegmentTree:"""A data structure that can answer point update & range minimum queries."""def __init__(self, len_: int):self.len = len_self.tree = [0] * (2 * len_)def set(self, ind: int, val: int) -> None:"""Sets the value at ind to val."""ind += self.len

### Solution - Dynamic Range Sum Queries

C++

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

and how we combine the elements.

#include <iostream>#include <vector>using std::cout;using std::endl;using std::vector;Code Snippet: Segment Tree (Click to expand)int main() {

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 to 0.

Code Snippet: Segment Tree (Click to expand)arr_len, query_num = map(int, input().split())arr = list(map(int, input().split()))segtree = SumSegmentTree(arr_len)for i, v in enumerate(arr):segtree.set(i, v)

## 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++

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

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;

Python

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

## $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 | |||

KACTL | 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

C++

Using an indexed set, we can solve this in just a few lines.

#include <bits/stdc++.h>using namespace std;#include <ext/pb_ds/assoc_container.hpp>using namespace __gnu_pbds;template <class T>using Tree =tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;int main() {

Note that if it were not the case that all elements of the input array were
distinct, then this code would be incorrect since `Tree<int>`

would remove
duplicates. Instead, we would use an indexed set of pairs
(`Tree<pair<int,int>>`

), where the first element of each pair would denote the
value while the second would denote the position of the value in the array.

Java

Using a binary indexed tree, we can count the number of inversions.

import java.io.*;import java.util.*;public class Main {public static void main(String[] args) {final int MAX_ELEM = (int)1e7;Kattio io = new Kattio();int testNum = io.nextInt();for (int t = 0; t < testNum; t++) {

Python

Code Snippet: BIT (Click to expand)MAX_ELEM = 10**7test_num = int(input())for _ in range(test_num):bit = BIT(MAX_ELEM + 1)input()arr_len = int(input())

## 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 | |||

CF | Easy | ## Show TagsBinary Search, Offline, 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 | |||

Platinum | 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!