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

Contributor: Andrew Wang

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 $k$-th ElementOrder Statistic TreeWith a BITWith a Segment TreeExample - Inversion CountingSolutionRange Sum ProblemsGeneralUSACOFocus Problem – read through 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 – read through 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 | 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++

Note that `st.init(n+1)`

allows us to update and query indices in the range
`[0,n+1)=[0,n]`

.

#include <bits/stdc++.h>using namespace std;template<class T> struct Seg { // comb(ID,b) = bconst T ID = 1e18; T comb(T a, T b) { return min(a,b); }int n; vector<T> seg;void init(int _n) { n = _n; seg.assign(2*n,ID); }void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }void upd(int p, T val) { // set val at position pseg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }

Java

import java.util.*;import java.io.*;public class DynamicRangeMinQueries {public static void main(String[] args) {Kattio io = new Kattio();int n = io.nextInt();int q = io.nextInt();SegmentTree seg = new SegmentTree(n);

### Solution - Dynamic Range Sum Queries

C++

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

, `ID`

, and
`comb`

.

#include <bits/stdc++.h>using namespace std;template<class T> struct Seg { // comb(ID,b) = bconst T ID = 0; T comb(T a, T b) { return a+b; }int n; vector<T> seg;void init(int _n) { n = _n; seg.assign(2*n,ID); }void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }void upd(int p, T val) { // set val at position pseg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }

Java

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

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

to `long`

).

import java.util.*;import java.io.*;public class DynamicRangeSumQueries {public static void main(String[] args) {Kattio io = new Kattio();int n = io.nextInt();int q = io.nextInt();SegmentTree seg = new SegmentTree(n);

## Binary Indexed Tree

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 <bits/stdc++.h>using namespace std;using ll = long long;const int MX = 2e5+5;int n, q;vector<ll> bit(MX), x(MX);void upd(int i, ll v) {

#### Solution 2

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

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

CF | ||||

Benq | based off above |

/*** 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.util.*;import java.io.*;public class DynamicRangeSumQueries {static long[] bit;static int n;public static void main(String[] args) {Kattio io = new Kattio();n = io.nextInt();int q = io.nextInt();

## $k$-th Element

FindingSuppose 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 set 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 – read through 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!