# Point Update Range Sum

Authors: Benjamin Qi, Andrew Wang

### Prerequisites

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

Focus Problem – read through this problem before continuing!

Most gold range query problems require you to support following tasks in $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 $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 | |||
---|---|---|---|

CSA | Interactive updates. | ||

CPH | Same implementation as AICash below. | ||

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

cp-algo | Advanced versions will be covered in Plat. |

### Implementations

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

CF | simple implementation | ||

Benq | based off above |

C++

1template<class T> struct Seg { // comb(ID,b) = b2 const T ID = 0; T comb(T a, T b) { return a+b; }3 int n; vector<T> seg;4 void init(int _n) { n = _n; seg.assign(2*n,ID); }5 void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }6 void upd(int p, T val) { // set val at position p7 seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }8 T query(int l, int r) { // sum on interval [l, r]9 T ra = ID, rb = ID;10 for (l += n, r += n+1; l < r; l /= 2, r /= 2) {

Java

1import java.util.*;2import java.io.*;34public class segtree {5 public static final int N = (int) 1e5; // limit for array size6 public static int n; // array size7 public static long t[] = new long[2 * N];8 public static void main(String[] args) throws Exception {9 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));10 n = Integer.parseInt(br.readLine());

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

### Implementations

C++

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

CF | |||

Benq | based off above |

Java

1public static long[] fwt;2public static long query(int a, int b) {3 return sum(b) - sum(a - 1);4}5public static long sum(int i) {6 long sum = 0;7 while (i > 0) {8 sum += fwt[i];9 i -= (i & -i); //least important bit10 }

## Finding $k$-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 set locally, you need to install GCC as mentioned in Running Code.

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

### General

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

CSES | Easy | Show Sketch | |||

CSES | Easy | Show Sketch | |||

CSES | Easy | Show Sketch | |||

CSES | Easy | View Solution | |||

Kattis | Easy | Show Sketch | |||

CSES | Normal | Show Sketch |

### USACO

Haircut, Balanced Photo, and Circle Cross are just variations on inversion counting.

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

Gold | Easy | External Sol | |||

Gold | Easy | External Sol | |||

Gold | Easy | External Sol | |||

Gold | Easy | External Sol | |||

Plat | Easy | External Sol | |||

Old Gold | Hard | External Sol |