Segment tree and Binary Indexed Tree

Segment Tree

Is used in range query problems

Problem 1

Given an array $a_1, a_2, ..., a_n$, $n \leq 10^5$, and $q \leq 10^5$ queries $(l,r)$ that asked for the sum $\sum_{i=l}^r a_i$.

Solution

Create a prefix sum array $f_i = \sum_{j=1}^i a_j$
$f_1 = a_1$
$f_i = f_{i-1} + a_i$

Then $\sum_{i=l}^r a_i = f_r - f_{l-1}$

Overall complexity: $O(n+q)$

Problem 1 upgraded

There are now 2 types of queries:

• SUM $(l,r)$: asked for the sum $\sum_{i=l}^r a_i$.
• CHANGE $i$ $v$: change the value of $a_i$ to $v$

We cannot update $f$ naively after type-2 queries
$\Rightarrow$ We need a data structure called Segment Tree

Create a Segment Tree:

• Each node of the tree manages an interval $(l,r)$
• Store the sum $\sum_{i=l}^r a_i$.
• Store the references to node $(l,m)$ and node $(m,r)$ with $m = \frac{l+r}{2}$

Some operations that Segment Tree can do:

• Update the value of an element and the sum of related intervals in $O(\log_2{n})$ time.
• Get the sum of an interval in $O(\log_2{n})$ time

It can be proved that there will be at most $4n$ nodes in Segment Tree.

Fenwick Tree (Binary Indexed Tree)

A magical tree that uses the properties of the binary representations of numbers.

int updateBIT(int x,int v)

void getBIT(int x)
{

}

Some operations of Binary Indexed Tree

Comparison between Segment Tree (ST) and Binary Indexed Tree (BIT)

In Competitive Programming III

ST:

• Initialization: $O(n)$.
• Update a single point and get an interval operations: $O(\log{n})$ complexity.
• Can do all types of $(l,r)$ queries
• Drawback: Longer codes, larger constant factor.
• Can use lazy update technique to do range update in $O(\log{n})$ complexity, as long as you can calculate the new result of an interval based on the information in the query.
  BIT:
• Initialization: $O(n\log{n})$.
• Drawback: Can only do $(1,x)$ queries $\Rightarrow$ Cannot find $\min_{i=l}^r a_i$ because we cannot find $\min_{i=l}^r a_i$ from $\min_{i=1}^{l-1} a_i$ and $\min_{i=1}^r a_i$.