using System;

using System.Diagnostics;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

        const int upperBound = 10001;

​

        var stopwatch = new Stopwatch();           

        var bst = new BinarySearchTree();

        var numbers = Enumerable.Range(1, upperBound).ToArray();

        var randomGenerator = new Random();

​

        Shuffle(numbers, randomGenerator);

​

        stopwatch.Start();

        foreach (var number in numbers)

        {

            if (randomGenerator.Next(0, 100) < 50)

            {

                bst.Add(number, number);

            }

            else

            {

                bst.AddUp(number, number);

            }

        }

        stopwatch.Stop();

        Console.WriteLine("Added(up) {0} values in: {1} ms, {2} ticks", upperBound - 1, stopwatch.ElapsedMilliseconds, stopwatch.ElapsedTicks);

​

        Shuffle(numbers, randomGenerator);

        stopwatch.Reset();

​

        stopwatch.Start();

        foreach (var number in numbers)

        {

            if (randomGenerator.Next(0, 100) < 50)

            {

                bst.GetValue(number);

            }

            else

            {

                bst.GetSum(number);

            }

        }

        stopwatch.Stop();

        Console.WriteLine("Got {0} values in: {1} ms, {2} ticks", upperBound - 1, stopwatch.ElapsedMilliseconds, stopwatch.ElapsedTicks);

​

        Console.ReadLine();

    }

​

    static void Shuffle<T>(T[] array, Random rnd)

    {

        int n = array.Length;

        while (n > 0)

        {

            int k = rnd.Next(n--);

            Swap(array, k, n);

        }

    }

​

    static void Swap<T>(T[] array, int left, int right)

    {

        T oldLeft = array[left];

        array[left] = array[right];

        array[right] = oldLeft;

    }

}

​

class BinarySearchTree

{

    private Node Root;

​

    private class Node

    {

        public int Key { get; set; }

        public int Value { get; set; }

        public int Sum { get; set; }

​

        public Node Left { get; set; }

        public Node Right { get; set; }

​

        public Node(int key, int value, int sum)

        {

            Key = key;

            Value = value;

            Sum = sum;

        }

    }

​

    private int Sum(Node node)

    {

        if (node == null)

        {

            return 0;

        }

​

        return node.Sum;

    }

​

    public int GetValue(int key)

    {

        return Get(Root, key).Value;

    }

​

    public int GetSum(int key)

    {

        return Get(Root, key).Sum;

    }

​

    private Node Get(Node node, int key)

    {

        if (node == null)

        {

            return null;

        }

​

        if (key < node.Key)

        {

            return Get(node.Left, key);

        }

        else if (key > node.Key)

        {

            return Get(node.Right, key);

        }

        else

        {

            return node;

        }

    }

​

public void Add(int key, int value)

{

    Root = Add(Root, key, value);

}

​

private Node Add(Node node, int key, int value)

{

    if (node == null)

    {

        node = new Node(key, value, value);

    }

​

    if (key < node.Key)

    {

        node.Left = Add(node.Left, key, value);

    }

    else if (key > node.Key)

    {

        node.Right = Add(node.Right, key, value);

    }

    else

    {

        node.Value = value;

    }

​

    node.Sum = Sum(node.Left) + Sum(node.Right) + node.Value;

​

    return node;

}

​

    public void AddUp(int key, int value)

    {

        Root = AddUp(Root, key, value);

    }

​

    private Node AddUp(Node node, int key, int value)

    {

        if (node == null)

        {

            node = new Node(key, value, value);

        }

​

        if (key < node.Key)

        {

            node.Value += value;

            node.Left = AddUp(node.Left, key, value);

        }

        else if (key > node.Key)

        {

            node.Value += value;

            node.Right = AddUp(node.Right, key, value);

        }

        else

        {

            node.Value = value;

        }

​

        node.Sum = Sum(node.Left) + Sum(node.Right) + node.Value;

        return node;

    }

}