seg Tree Algorithm
The Segment Tree Algorithm is an advanced data structure that allows efficient processing of queries and modifications on an array or a list. It is particularly useful in scenarios where we need to perform range-based operations, such as finding the minimum or maximum value, calculating the sum or the greatest common divisor within a specific range of elements in an array. The main advantage of the Segment Tree Algorithm is its ability to perform these operations in logarithmic time complexity, making it a popular choice for handling large datasets in competitive programming and other applications.
The Segment Tree Algorithm constructs a binary tree, where each node represents an interval or segment of the input array. The root node represents the entire array, and its children represent two equal halves of the array. This structure continues recursively until each leaf node represents a single element of the array. The tree is typically stored in an array, making it easy to traverse and update. To process a query or perform a modification, the algorithm uses a divide and conquer approach, splitting the requested range into smaller sub-ranges that can be combined to produce the final result. This efficient approach allows the Segment Tree Algorithm to handle both static and dynamic arrays, supporting updates and queries in O(log n) time complexity, where n is the number of elements in the array.
//#include <bits/stdc++.h>
#incldue <iostream>
#define MAX 4000000
using namespace std;
typedef long long ll;
void ConsTree(ll arr[], ll segtree[], ll low, ll high, ll pos)
{
if (low == high)
{
segtree[pos] = arr[low];
return;
}
ll mid = (low + high) / 2;
ConsTree(arr, segtree, low, mid, 2 * pos + 1);
ConsTree(arr, segtree, mid + 1, high, 2 * pos + 2);
segtree[pos] = segtree[2 * pos + 1] + segtree[2 * pos + 2];
}
ll query(ll segtree[], ll lazy[], ll qlow, ll qhigh, ll low, ll high, ll pos)
{
if (low > high)
return 0;
if (qlow > high || qhigh < low)
return 0;
if (lazy[pos] != 0)
{
segtree[pos] += lazy[pos] * (high - low + 1);
if (low != high)
{
lazy[2 * pos + 1] += lazy[pos];
lazy[2 * pos + 2] += lazy[pos];
}
lazy[pos] = 0;
}
if (qlow <= low && qhigh >= high)
return segtree[pos];
ll mid = (low + high) / 2;
return query(segtree, lazy, qlow, qhigh, low, mid, 2 * pos + 1) + query(segtree, lazy, qlow, qhigh, mid + 1, high, 2 * pos + 2);
}
void update(ll segtree[], ll lazy[], ll start, ll end, ll delta, ll low, ll high, ll pos)
{
if (low > high)
return;
if (lazy[pos] != 0)
{
segtree[pos] += lazy[pos] * (high - low + 1);
if (low != high)
{
lazy[2 * pos + 1] += lazy[pos];
lazy[2 * pos + 2] += lazy[pos];
}
lazy[pos] = 0;
}
if (start > high || end < low)
return;
if (start <= low && end >= high)
{
segtree[pos] += delta * (high - low + 1);
if (low != high)
{
lazy[2 * pos + 1] += delta;
lazy[2 * pos + 2] += delta;
}
return;
}
ll mid = (low + high) / 2;
update(segtree, lazy, start, end, delta, low, mid, 2 * pos + 1);
update(segtree, lazy, start, end, delta, mid + 1, high, 2 * pos + 2);
segtree[pos] = segtree[2 * pos + 1] + segtree[2 * pos + 2];
}
int main()
{
ll n, c;
scanf("%lld %lld", &n, &c);
ll arr[n] = {0}, p, q, v, choice;
ll segtree[MAX], lazy[MAX] = {0};
ConsTree(arr, segtree, 0, n - 1, 0);
while (c--)
{
scanf("%lld", &choice);
if (choice == 0)
{
scanf("%lld %lld %lld", &p, &q, &v);
update(segtree, lazy, p - 1, q - 1, v, 0, n - 1, 0);
}
else
{
scanf("%lld %lld", &p, &q);
printf("%lld\n", query(segtree, lazy, p - 1, q - 1, 0, n - 1, 0));
}
}
return 0;
}
