Segment Tree tutorial - convert C programming language to C# - http://contest.cs.cmu.edu/295/tutorials/seg_tree.cc

SegmentTreeTutorial_1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace segmentTree
{
    /*
     * This code illustrates a segment tree which solves the following problem:
     *
     *     maintain a list of values a0, a1 ... a(n-1) (n fixed) which supports
     *        ai <- x
     *        sum of the elements ai+a(i+1)+...+aj
     *
     * Segment trees can be used to solve a much wider range of problems.
     * For example, it can be adapted to handle the ability to add a constant
     * to all the varaibles in some range.  That is for another set of notes.
     * 
     * First we round up n to N, which is a power of two.  We allocate an
     * array of 2N integers.  This array implicitly represents a tree with
     * the root at position 1, and the leaves are positions N, N+1, N+2,
     * ... 2*N-1.  To move from a node i to its parent we compute
     * floor(i/2).  To move from a node j to its left child we compute
     * 2*j, and to move to its right child we compute 2*j+1.  The
     * following diagram illustrates this for N=4.
     * 
     *                 1
     *                / \
     *               /   \
     *              2     3
     *             / \   / \
     *            4   5 6   7
     *
     * The number shown at a node is the index of that node in the array.
     *
     * So if we're at node j=3 and then 2*j=6, which is the left child
     * and 2*j+1=7 which is the right child.  Similarly if we're at i=6
     * or i=7, then i/2 = 3 which is the parent of i.
     *
     * So to solve the problem at hand, we store the values of the a's in
     * the leaves of the tree.  In each internal node we store the sum of
     * all the a values in the subtree rooted there.
     *
     * For example, suppose that the a values are 2 1 3 2.  Then here is
     * what is stored in the tree (a.k.a. array):
     *
     *                 8
     *                / \
     *               /   \
     *              3     5
     *             / \   / \
     *            2   1 3   2
     *
     * Note that the internal nodes of the tree represent the sum of
     * certain ranges of the array a.  To add a number c to the value of a
     * leaf node, we have to add the same c to all the nodes on the path
     * from that leaf to the root.  The clever function f() below it
     * elegantly computes the sum of any range a[i...j] doing only O(log
     * n) work.
     * 
     *           Danny Sleator <sleator@cs.cmu.edu> 
     *           September, 2015
     */

    /*
     * Jianmin Chen 
     * Work on the tutorial on Oct. 20, 2016
     * 
     */
    class segmentTreeTutorial
    {        
        public static int K = 10;
        public static int MAXN = 1 << K;

        public static int[] A = new int[2 * MAXN];

        public static int parent(int v) { return v / 2; }
        public static int lc(int v) { return 2 * v; }
        public static int rc(int v) { return 2 * v + 1; }

        // We want to assign the value of A[v] to x.
        // This is the same as doing the assignment A[v] += x-A[v]
        // To achieve this we have to add this quantity to
        // every node on the path from v to the root.
        static void assign(int v, int x)
        {            
            x = x - A[MAXN + v];

            for (int j = MAXN + v; j > 0; j = parent(j)) 
                A[j] += x;
        }

        // [l,r] is the range represented by the leaves at
        // the bottom of the subtree rooted at v.
        // [ql,qr] is the query range.  It's always within [l,r]
        public static int f(int v, int l, int r, int ql, int qr)
        {            
            int m = (l + r) / 2;  // left range is [l,m].  right range is [m+1,r]

            Console.WriteLine("v={0}, l={1}, r={2}, ql={3}, qr={4}\n", v, l, r, ql, qr);

            if (l == ql && r == qr) 
                return A[v];

            int total = 0;
            if (ql <= m)
                total += f(lc(v), l, m, ql, Math.Min(m, qr));

            if (qr > m)
                total += f(rc(v), m + 1, r, Math.Max(ql, m + 1), qr);

            return total;
        }

        public static int sum(int i, int j)
        {
            return f(1, 0, MAXN - 1, i, j);
        }

        static void Main(string[] args)
        {
            for (int i = 0; i < 4; i++)
            {
                assign(i, 2 * i);
            }

            Console.WriteLine("sum(2,3) = {0}\n", sum(2, 3));
            Console.WriteLine("sum(0,2) = {0}\n", sum(0, 2));
            assign(3, 239);
            Console.WriteLine("sum(3,3) = {0}\n", sum(3, 3));
        }
    }
}