Skip to content

Instantly share code, notes, and snippets.

@jigargandhi

jigargandhi/IntervalTrees.cs

Last active November 9, 2017 04:36
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jigargandhi/5636e026822ffb65e9203868f7c86b4e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jigargandhi/5636e026822ffb65e9203868f7c86b4e to your computer and use it in GitHub Desktop.
Download ZIP
Segment Trees
Raw
IntervalTrees.cs
using System;
class Program
{
static void Main(string[] args)
{
int[] values = new int[] { 1, 19, 9, 45, 20, 36, 35 };
IntervalTree tree = new IntervalTree(values);
tree.Build();
int x = tree.Query(1, 6);
Console.WriteLine(string.Join(",", values));
Console.WriteLine(x);
tree.Update(3, 30);
x= tree.Query(3, 6);
Console.WriteLine(x);
Console.ReadKey();
}
}
class IntervalNode
{
public int lowerIndex;
public int higherIndex;
public int value;
public IntervalNode Left;
public IntervalNode Right;
}
class IntervalTree
{
private int[] store;
IntervalNode root;
public IntervalTree(int[] array)
{
store = array;
}
public void Build()
{
IntervalNode node = new IntervalNode();
node.lowerIndex = 0;
node.higherIndex = store.Length - 1;
node.value = Insert(node);
root = node;
}
private int Insert(IntervalNode node)
{
if (node.lowerIndex == node.higherIndex)
{
node.value = store[node.lowerIndex];
}
else
{
node.Left = new IntervalNode();
node.Left.lowerIndex = node.lowerIndex;
int mid = (node.lowerIndex + node.higherIndex) / 2;
node.Left.higherIndex = mid;
node.Right = new IntervalNode();
node.Right.lowerIndex = mid + 1;
node.Right.higherIndex = node.higherIndex;
node.value = Math.Min(Insert(node.Left), Insert(node.Right));
}
return node.value;
}
public int Query(int low, int high)
{
return QueryInternal(root, low, high);
}
private int QueryInternal(IntervalNode node, int low, int high)
{
if (low <= node.lowerIndex && node.higherIndex <= high)
return node.value;
if (high < node.lowerIndex || low > node.higherIndex)
return int.MaxValue;
int min = Math.Min(QueryInternal(node.Left, low, high), QueryInternal(node.Right, low, high));
return min;
}
public void Update(int index, int value)
{
UpdateInternal(root, index, value);
store[index] = value;
}
private void UpdateInternal(IntervalNode node, int index, int value)
{
if (node.lowerIndex <index && index < node.higherIndex)
{
node.value = Math.Min(node.value, value);
}
if (node.higherIndex == index && node.lowerIndex == index)
{
node.value = value;
return;
}
int mid = (node.lowerIndex + node.higherIndex) / 2;
if (index <= mid)
{
UpdateInternal(node.Left, index, value);
}
else
{
UpdateInternal(node.Right, index, value);
}
}
}
Raw
SegmentTree.cs
class SegmentTree
{
private int[] tree;
private int[] array;
private int max_size = 0;
public SegmentTree(int length, int[] array)
{
int x = (int)(Math.Ceiling(Math.Log(length, 2)));
//Maximum size of segment tree
max_size = 2 * (int)Math.Pow(2, x) - 1;
tree = new int[max_size + 1];
this.array = array;
}
public void Construct()
{
ConstructUtil(0, array.Length - 1, 0);
}
private static int getMid(int s, int e) { return s + (e - s) / 2; }
private int ConstructUtil(int startIndex, int endIndex, int segmentTreeIndex)
{
if (startIndex == endIndex)
{
tree[segmentTreeIndex] = array[startIndex];
return tree[segmentTreeIndex];
}
int mid = getMid(startIndex, endIndex);
int left = ConstructUtil(startIndex, mid, 2 * segmentTreeIndex + 1);
int right = ConstructUtil(mid + 1, endIndex, 2 * segmentTreeIndex + 2);
tree[segmentTreeIndex] = Merge(left, right);
return tree[segmentTreeIndex];
}
private int Merge(int left, int right)
{
return Math.Max(left, right);
}
public int Query(int queryStart, int queryEnd)
{
return QueryUtil(0, array.Length - 1, queryStart, queryEnd, 0);
}
private int QueryUtil(int segmentStart, int segmentEnd, int queryStart, int queryEnd, int treeIndex)
{
if (queryStart <= segmentStart && queryEnd >= segmentEnd)
{
return tree[treeIndex];
}
if (queryEnd < segmentStart || queryStart > segmentEnd)
{
return 0;
}
int mid = getMid(segmentStart, segmentEnd);
int left = QueryUtil(segmentStart, mid, queryStart, queryEnd, treeIndex * 2 + 1);
int right = QueryUtil(mid + 1, segmentEnd, queryStart, queryEnd, treeIndex * 2 + 2);
return Merge(left, right);
}
public void Update(int arrayIndex, int newVal)
{
array[arrayIndex] = newVal;
UpdateUtil(0, array.Length - 1, arrayIndex, newVal, 0);
}
private void UpdateUtil(int segmentStart, int segmentEnd, int index, int newVal, int treeIndex)
{
if (segmentEnd == segmentStart && segmentStart == index)
{
tree[treeIndex] = newVal;
return;
}
if (newVal > tree[treeIndex])
{
tree[treeIndex] = newVal;
}
int mid = getMid(segmentStart, segmentEnd);
if (index <= mid)
{
UpdateUtil(segmentStart, mid, index, newVal, 2 * treeIndex + 1);
}
else
{
UpdateUtil(mid + 1, segmentEnd, index, newVal, 2 * treeIndex + 2);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment