Segment Tree Algorithm
Segment Tree Algorithm is a versatile data structure that enables efficient querying and modification of an array, particularly for range queries. This tree-based algorithm is particularly useful when dealing with large data sets, as it allows for both storage and manipulation of the data in a structured manner. The concept behind the Segment Tree Algorithm is to divide the given array into multiple segments or intervals, which are then represented by nodes in a binary tree. Each node in the tree contains information about a specific segment, such as the sum, minimum, or maximum value of the elements in that interval. The leaf nodes of the tree represent individual elements of the array, while the internal nodes represent the combined information of their child nodes.
The primary operations supported by the Segment Tree Algorithm are building the tree, updating an element in the array, and querying a range. Building the tree involves initializing the leaf nodes with the corresponding array elements and then recursively combining the information of the child nodes to find the value for each parent node. Updating an element involves traversing the tree from the root to the leaf node representing that element and changing the values of any nodes affected by the update. Querying a range involves traversing the tree from the root to the leaf nodes in the desired interval, gathering the relevant information from each node encountered and combining this information to compute the overall query result. Overall, the Segment Tree Algorithm enables efficient range queries and updates, making it a valuable tool for a variety of applications in computer science and other fields.
/*
Petar 'PetarV' Velickovic
Data Structure: Segment Tree
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MID (left+right)/2
#define MAX_N 1000001
#define MAX_TREE (MAX_N << 2)
#define INF 987654321
using namespace std;
typedef long long lld;
int n;
int niz[MAX_N];
int ST[MAX_TREE];
//Segmentno stablo nad datim nizom - u datom primeru cuva se minimum nad svakim segmentom
//Slozenost: InitTree O(N), Update O(log N), Query O(log N)
void InitTree(int idx, int left, int right)
{
if (left == right)
{
ST[idx] = niz[left];
return;
}
InitTree(2*idx, left, MID);
InitTree(2*idx+1, MID+1, right);
ST[idx] = min(ST[2*idx], ST[2*idx+1]);
}
void Update(int idx, int x, int val, int left, int right)
{
if (left == right)
{
ST[idx] = val;
return;
}
if (x <= MID) Update(2*idx, x, val, left, MID);
else Update(2*idx+1, x, val, MID+1, right);
ST[idx] = min(ST[2*idx], ST[2*idx+1]);
}
int Query(int idx, int l, int r, int left, int right)
{
if (l <= left && right <= r) return ST[idx];
int ret = INF;
if (l <= MID) ret = min(ret, Query(2*idx, l, r, left, MID));
if (r > MID) ret = min(ret, Query(2*idx+1, l, r, MID+1, right));
return ret;
}
int main()
{
n = 6;
niz[1] = 4;
niz[2] = 2;
niz[3] = 5;
niz[4] = 1;
niz[5] = 6;
niz[6] = 3;
InitTree(1, 1, n);
printf("%d\n",Query(1, 1, 3, 1, n));
Update(1, 4, 10, 1, n);
Update(1, 5, 0, 1, n);
printf("%d\n",Query(1, 4, 6, 1, n));
return 0;
}
