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

namespace Clover.Algoritms.DataStructure
{
    public class TreeArray
    {
        private double[] items;

        private double[] data;
        public TreeArray(double[] data)
        {
            if (data == null || data.Length == 0)
                throw new ArgumentNullException("data");

            this.items = new double[data.Length];
            this.data = data;

            for (int i = 1; i <= items.Length; i++)
            {
                int start = i - Lowbit(i);
                double sum = 0;
                while (start < i)
                {
                    sum += data[start];
                    start++;
                }
                items[i - 1] = sum;
            }
        }
        public double Sum(int k)
        {
            double ret = 0;
            while (k > 0)
            {
                ret += items[k - 1];
                k -= Lowbit(k);
            }
            return ret;
        }
        public void Update(int k, int value)
        {
            int x = k - 1;
            var oldValue = this.data[x];
            this.data[x] = value;

            for (int i = x; i < items.Length; i += Lowbit(i + 1))
            {

                items[i] = items[i] - oldValue + value;
            }
        }

        public static int Lowbit(int i)
        {
            return i & -i;
        }
    }
}