PrevNext
Somewhat Frequent
 0/15

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.

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

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

  • 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 O(logN)\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 sys
class SegmentTree:
"""A data structure that can answer point update & range minimum queries."""
def __init__(self, arr: list[int], n: int) -> None:
self.arr = arr
self.n = n
self.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 sys
class SegmentTree:
def __init__(self, arr: list[int], n: int) -> None:
self.arr = arr
self.n = n
self.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 sys
class BIT:
"""
Short for "binary indexed tree",
this data structure supports point update and range sum
queries 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.

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;

Finding the kk-th Element

Suppose 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][1,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 10910^9), then you should apply coordinate compression before using a BIT or segment tree (though sparse segment trees do exist).

General

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsPURS
KattisEasy
Show TagsInversions, PURS
CSESEasy
Show TagsPURS
CSESEasy
Show TagsCoordinate Compress, PURS
CSESEasy
Show TagsCoordinate Compress, PURS
CSESNormal
Show TagsOffline, PURS

USACO

StatusSourceProblem NameDifficultyTags
GoldEasy
Show TagsInversions, PURS
GoldEasy
Show TagsInversions, PURS
GoldEasy
Show TagsInversions, PURS
GoldEasy
Show TagsPURS
PlatEasy
Show TagsInversions, PURS
Old GoldHard
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!

PrevNext