Tree Data Structure

Segment Tree

A segment tree is typically used to store a set of intervals, such as the start and end times of events or the positions of objects in a two-dimensional space.

• Each node in the tree represents a particular interval, and the children of a node represent sub-intervals of the parent interval
• Allows for efficient querying and updating of the data, as the tree can be searched and traversed to find the relevant intervals.

This is a segment tree problem that I couldn’t do at a contest:

• https://codeforces.com/contest/2050/problem/F

Resources:

• https://cp-algorithms.com/data_structures/segment_tree.html

4 N or 2N?

Eric Pei reports 4N to be faster https://ericpei.ca/posts/segment-tree/

Todo problems:

• https://codeforces.com/blog/entry/71925
• https://codeforces.com/blog/entry/22616

A Segment Tree is a more general Fenwick Tree that can support other queries (more than range queries), such as a Range Minimum Query (RMQ).

Implementation

Erichto gave a really good visualization, see it as a binary tree.

We store a segment tree as an array of $2n$ elements where $n$ is the size of the original array and a power of two.

The tree nodes are stored from top to bottom:

• tree[1] is the top node, tree[2] and tree[3] are its children, and so on
• tree[n] to tree[2n−1] correspond to the values of the original array on the bottom level of the tree

To access the child and parents:

• Parent: the parent of tree[k] $\leftarrow$ tree[k/2]
• Children: tree[k] $\to$ tree[2k] and tree[2k+1]
  • even = left child
  • odd = right child

We always want to be on the left child node for the left side, and right child node on the right side so that the parent is representative.

Why use 1-indexing?

When we do Heap as an array, it seems to be 0-indexed. Both work. If you do 0-indexed,you need to use $2k+1$ instead of $2k$ to get the children node.

To construct the tree

for (int i=0;i<m;i++) {
	cin >> p_min[m+i];
	p_max[m+i] = p_min[m+i];
}
for (int i=m-1;i>=0; i--) {
	p_min[i] = min(p_min[2*i], p_min[2*i + 1]);
	p_max[i] = max(p_max[2*i], p_max[2*i + 1]);
}

Operations:

int sum(int a, int b) { 
	a += n; 
	b += n; 
	int s = 0; 
	while (a <= b) { 
		if (a%2 == 1) s += tree[a++]; 
		if (b%2 == 0) s += tree[b--]; 
		a /= 2; // Climb up to parent
		b /= 2;
	
	} 
	return s; 
}
 
void add(int k, int x) { 
	k += n; tree[k] += x; 
	for (k /= 2; k >= 1; k /= 2) { 
		tree[k] = tree[2*k]+tree[2*k+1]; 
	} 
}

Segment tree as a class, saw from this submission https://codeforces.com/contest/2050/submission/295083798

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vvvi vector<vector<vector<ll>>>
#define mll map<ll, ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define sz size()
#define f first
#define s second
#define nl endl
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define INF 1e9
#define min_pq priority_queue<ll, vector<ll>, greater<ll>>
#define init(a,n) for(ll i=0; i<n; i++) { cin>>a[i]; }
#define print(a) for(const auto&i: (a)){cerr<<i<<" ";}cerr<<nl;
 
 
class SegmentTree {
    vll seg;
    ll n;
 
public:
    SegmentTree(ll n) {
        this->n = n;
        seg.resize(4 * n, 0);
    }
 
    void build(const vll &v) {
        build(0, 0, n - 1, v);
    }
 
    ll query(ll l, ll r) {
        return query(0, 0, n - 1, l, r);
    }
 
private:
    void build(ll index, ll low, ll high, const vll &v) {
        if (low == high) {
            seg[index] = v[low];
            return;
        }
        ll mid = low + (high - low) / 2;
        build(2 * index + 1, low, mid, v);
        build(2 * index + 2, mid + 1, high, v);
        seg[index] = gcd(seg[2 * index + 1], seg[2 * index + 2]);
    }
 
    ll query(ll index, ll low, ll high, ll l, ll r) {
        if (l > high || r < low) return 0; 
        if (low >= l && high <= r) return seg[index];
        ll mid = low + (high - low) / 2;
        ll left = query(2 * index + 1, low, mid, l, r);
        ll right = query(2 * index + 2, mid + 1, high, l, r);
        return gcd(left, right);
    }
 
    ll gcd(ll a, ll b) {
        while (b) {
            ll temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};
 
void solve() {
    ll n, q;
    cin >> n >> q;
 
    vll a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    
    if (n == 1) {
        while (q--) {
            ll l, r;
            cin >> l >> r;
            cout << "0 "; 
        }
        cout<<nl;
        return;
    }
 
    vll diff(n - 1);
    for (ll i = 0; i < n - 1; i++) {
        diff[i] = abs(a[i + 1] - a[i]);
    }
 
    
    SegmentTree segTree(n - 1);
    segTree.build(diff);
 
    
    while (q--) {
        ll l, r;
        cin >> l >> r;
        --l, --r;
 
        if (l == r) {
            cout << "0 "; 
        } else {
            cout << segTree.query(l, r - 1) << " "; 
        }
    }
    cout<<nl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}