SegmentTreeApply.cs

using System;

namespace DataStructures.SegmentTrees;

/// <summary>
///     This is an extension of a segment tree, which allows applying distributive operations to a subarray
///     (in this case multiplication).
/// </summary>
public class SegmentTreeApply : SegmentTree
{
    /// <summary>
    ///     Initializes a new instance of the <see cref="SegmentTreeApply" /> class.
    ///     Runtime complexity: O(n) where n equals the array-length.
    /// </summary>
    /// <param name="arr">Array on which the operations should be made.</param>
    public SegmentTreeApply(int[] arr)
        : base(arr)
    {
        // Initilizes and fills "operand" array with neutral element (in this case 1, because value * 1 = value)
        Operand = new int[Tree.Length];
        Array.Fill(Operand, 1);
    }

    /// <summary>
    ///     Gets an array that stores for each node an operand,
    ///     which must be applied to all direct and indirect child nodes of this node
    ///     (but not to the node itself).
    /// </summary>
    public int[] Operand { get; }

    /// <summary>
    ///     Applies a distributive operation to a subarray defined by <c>l</c> and <c>r</c>
    ///     (in this case multiplication by <c>value</c>).
    ///     Runtime complexity: O(logN) where N equals the initial array-length.
    /// </summary>
    /// <param name="l">Left border of the subarray.</param>
    /// <param name="r">Right border of the subarray.</param>
    /// <param name="value">Value with which each element of the interval is calculated.</param>
    public void Apply(int l, int r, int value)
    {
        // The Application start at node with 1
        // Node with index 1 includes the whole input subarray
        Apply(++l, ++r, value, 1, Tree.Length / 2, 1);
    }

    /// <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>
    protected override int Query(int l, int r, int a, int b, int i)
    {
        if (l <= a && b <= r)
        {
            return Tree[i];
        }

        if (r < a || b < l)
        {
            return 0;
        }

        var m = (a + b) / 2;

        // Application of the saved operand to the direct and indrect child nodes
        return Operand[i] * (Query(l, r, a, m, Left(i)) + Query(l, r, m + 1, b, Right(i)));
    }

    /// <summary>
    ///     Applies the operation.
    /// </summary>
    /// <param name="l">Left border of the Application.</param>
    /// <param name="r">Right border of the Application.</param>
    /// <param name="value">Multiplier by which the subarray is to be multiplied.</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>
    private void Apply(int l, int r, int value, int a, int b, int i)
    {
        // If a and b are in the (by l and r) specified subarray
        if (l <= a && b <= r)
        {
            // Applies the operation to the current node and saves it for the direct and indirect child nodes
            Operand[i] = value * Operand[i];
            Tree[i] = value * Tree[i];
            return;
        }

        // If a or b are out of the by l and r specified subarray stop application at this node
        if (r < a || b < l)
        {
            return;
        }

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

        // Applies the operation to both halfes
        Apply(l, r, value, a, m, Left(i));
        Apply(l, r, value, m + 1, b, Right(i));

        // Recalculates the value of this node by its (possibly new) children.
        Tree[i] = Operand[i] * (Tree[Left(i)] + Tree[Right(i)]);
    }
}