SegmentTreeUpdate.cs

namespace DataStructures.SegmentTrees;

/// <summary>
///     This is an extension of a segment tree, which allows the update of a single element.
/// </summary>
public class SegmentTreeUpdate : SegmentTree
{
    /// <summary>
    ///     Initializes a new instance of the <see cref="SegmentTreeUpdate" /> class.
    ///     Runtime complexity: O(n) where n equals the array-length.
    /// </summary>
    /// <param name="arr">Array on which the queries should be made.</param>
    public SegmentTreeUpdate(int[] arr)
        : base(arr)
    {
    }

    /// <summary>
    ///     Updates a single element of the input array.
    ///     Changes the leaf first and updates its parents afterwards.
    ///     Runtime complexity: O(logN) where N equals the initial array-length.
    /// </summary>
    /// <param name="node">Index of the node that should be updated.</param>
    /// <param name="value">New Value of the element.</param>
    public void Update(int node, int value)
    {
        Tree[node + Tree.Length / 2] = value;
        Propagate(Parent(node + Tree.Length / 2));
    }

    /// <summary>
    ///     Recalculates the value of node by its children.
    ///     Calls its parent to do the same.
    /// </summary>
    /// <param name="node">Index of current node.</param>
    private void Propagate(int node)
    {
        if (node == 0)
        {
            // passed root
            return;
        }

        Tree[node] = Tree[Left(node)] + Tree[Right(node)];
        Propagate(Parent(node));
    }
}