Structure : Segment Tree
Segment tree is a data structure, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed. O(n) preprocessing O(log n) query
Segment tree stores intervals, and optimized for "which of these intervals contains a given point" queries.
One of the most common applications of the segment tree is the solution to the range minimum query problem. For certain types of segment trees, range updates are possible. Lazy propagation is a technique that allows range updates to be carried out with the same asymptotic time complexity, O(log n), as individual updates.
|
|
|
|
// -----------------------------------------------------------------------------
// Segment Tree C#
// -----------------------------------------------------------------------------
class SegmentTree
{
int n;
int[] lo, hi;
int[] post;
int npost;
long[] min, delta;
public SegmentTree(int n)
{
this.n = n;
lo = new int[n * 4 + 1];
hi = new int[n * 4 + 1];
post = new int[n * 2 + 1];
npost = 0;
min = new long[n * 4 + 1];
delta = new long[n * 4 + 1];
Init(1, 0, n - 1);
}
public SegmentTree(long[] a) : this(a.Length)
{
while (npost > 0)
{
int i = post[--npost];
if (lo[i] == hi[i])
min[i] = a[lo[i]];
else
Update(i);
}
}
public void Add(int a, int b, long val)
{
Add(1, a, b, val);
}
public long Min(int a, int b)
{
return Min(1, a, b);
}
void Init(int i, int a, int b)
{
post[npost++] = i;
lo[i] = a;
hi[i] = b;
if (a == b) return;
int m = (a + b) / 2;
Init(i * 2, a, m);
Init(i * 2 + 1, m + 1, b);
}
void Prop(int i)
{
delta[i * 2] += delta[i];
delta[i * 2 + 1] += delta[i];
delta[i] = 0;
}
void Update(int i)
{
min[i] = System.Math.Min(min[i * 2] + delta[i * 2],
min[i * 2 + 1] + delta[i * 2 + 1]);
}
void Add(int i, int a, int b, long val)
{
if (b < lo[i] || hi[i] < a) return;
if (a <= lo[i] && hi[i] <= b) {
delta[i] += val;
return;
}
Prop(i);
Add(i * 2, a, b, val);
Add(i * 2 + 1, a, b, val);
Update(i);
}
long Min(int i, int a, int b)
{
if (b < lo[i] || hi[i] < a) return int.MaxValue;
if (a <= lo[i] && hi[i] <= b) return min[i] + delta[i];
Prop(i);
long minLeft = Min(i * 2, a, b);
long minRight = Min(i * 2 + 1, a, b);
Update(i);
return System.Math.Min(minLeft, minRight);
}
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Segment Tree Python
# ------------------------------------------------------------------------------
class SegmentTree:
def __init__(self, n):
self._n = n
self._lo = [0] * (n * 4 + 1)
self._hi = [0] * (n * 4 + 1)
self._post = [0] * (n * 2 + 1)
self._npost = 0
self._dmin = [0] * (n * 4 + 1)
self._delta = [0] * (n * 4 + 1)
self._init(1, 0, n - 1)
@classmethod
def fill(cls, a):
c = cls(len(a))
while c._npost > 0:
c._npost -= 1
i = c._post[c._npost]
if c._lo[i] == c._hi[i]:
c._dmin[i] = a[c._lo[i]]
else:
c._update(i)
return c
def add(self, a, b, val):
self._add(1, a, b, val)
def min(self, a, b):
return self._min(1, a, b)
def _init(self, i, a, b):
self._post[self._npost] = i
self._npost += 1
self._lo[i] = a
self._hi[i] = b
if a == b: return
m = (a + b) // 2;
self._init(i * 2, a, m)
self._init(i * 2 + 1, m + 1, b)
def _prop(self, i):
self._delta[i * 2] += self._delta[i]
self._delta[i * 2 + 1] += self._delta[i]
self._delta[i] = 0
def _update(self, i):
self._dmin[i] = min(self._dmin[i * 2] + self._delta[i * 2],
self._dmin[i * 2 + 1] + self._delta[i * 2 + 1])
def _add(self, i, a, b, val):
if b < self._lo[i] or self._hi[i] < a: return
if a <= self._lo[i] and self._hi[i] <= b:
self._delta[i] += val
return
self._prop(i)
self._add(i * 2, a, b, val)
self._add(i * 2 + 1, a, b, val)
self._update(i)
def _min(self, i, a, b):
if b < self._lo[i] or self._hi[i] < a:
return 2 ** 63 - 1;
if a <= self._lo[i] and self._hi[i] <= b:
return self._dmin[i] + self._delta[i]
self._prop(i)
minLeft = self._min(i * 2, a, b)
minRight = self._min(i * 2 + 1, a, b)
self._update(i)
return min(minLeft, minRight)
# ------------------------------------------------------------------------------
Segment Tree 2D