SegmentTree.cs

usingSystem;

namespaceDataStructures.SegmentTrees;

/// <summary>
/// Goal: Data structure with which you can quickly perform queries on an array (i.e. sum of subarray)
/// and at the same time efficiently update an entry
/// or apply a distributive operation to a subarray.
/// Idea: Preprocessing special queries
/// Hint: The query operation HAS to be associative (in this example addition).
/// </summary>
publicclassSegmentTree
{
/// <summary>
/// Initializes a new instance of the <see cref="SegmentTree" /> class.
/// Runtime complexity: O(n) where n equals the array-length.
/// </summary>
/// <param name="arr">Array on which the queries should be made.</param>
publicSegmentTree(int[]arr)
{
// Calculates next power of two
varpow=(int)Math.Pow(2,Math.Ceiling(Math.Log(arr.Length,2)));
Tree=newint[2*pow];

// Transfers the input array into the last half of the segment tree array
Array.Copy(arr,0,Tree,pow,arr.Length);

// Calculates the first half
for(vari=pow-1;i>0;--i)
{
Tree[i]=Tree[Left(i)]+Tree[Right(i)];
}
}

/// <summary>Gets the segment tree array.</summary>
publicint[]Tree{get;}

/// <summary>
/// Starts a query.
/// Runtime complexity: O(logN) where n equals the array-length.
/// </summary>
/// <param name="l">Left border of the query.</param>
/// <param name="r">Right border of the query.</param>
/// <returns>Sum of the subarray between <c>l</c> and <c>r</c> (including <c>l</c> and <c>r</c>).</returns>
// Editing of query start at node with 1.
// Node with index 1 includes the whole input subarray.
publicintQuery(intl,intr)=>
Query(++l,++r,1,Tree.Length/2,1);

/// <summary>
/// Calculates the right child of a node.
/// </summary>
/// <param name="node">Current node.</param>
/// <returns>Index of the right child.</returns>
protectedintRight(intnode)=>2*node+1;

/// <summary>
/// Calculates the left child of a node.
/// </summary>
/// <param name="node">Current node.</param>
/// <returns>Index of the left child.</returns>
protectedintLeft(intnode)=>2*node;

/// <summary>
/// Calculates the parent of a node.
/// </summary>
/// <param name="node">Current node.</param>
/// <returns>Index of the parent node.</returns>
protectedintParent(intnode)=>node/2;

/// <summary>
/// Edits a query.
/// </summary>
/// <param name="l">Left border of the query.</param>
/// <param name="r">Right border of the query.</param>
/// <param name="a">Left end of the subarray enclosed by <c>i</c>.</param>
/// <param name="b">Right end of the subarray enclosed by <c>i</c>.</param>
/// <param name="i">Current node.</param>
/// <returns>Sum of a subarray between <c>l</c> and <c>r</c> (including <c>l</c> and <c>r</c>).</returns>
protectedvirtualintQuery(intl,intr,inta,intb,inti)
{
// If a and b are in the (by l and r) specified subarray
if(l<=a&&b<=r)
{
returnTree[i];
}

// If a or b are out of the by l and r specified subarray
if(r<a||b<l)
{
// Returns the neutral value of the operation
// (in this case 0, because x + 0 = x)
return0;
}

// Calculates index m of the node that cuts the current subarray in half
varm=(a+b)/2;

// Start query of new two subarrays a:m and m+1:b
// The right and left child cover this intervals
returnQuery(l,r,a,m,Left(i))+Query(l,r,m+1,b,Right(i));
}
}