면접 준비-C\#버 전의 트 리 배열

트 리 배열 은 임의의 연속 N 개의 값 과 시간 복잡 도 를 Log(n)로 계산 합 니 다.수정 도 Log(n)입 니 다.
일반 배열 의 수정 은 O(1)계산 과 O(n)이다.
구체 적 인 정 의 는 여 기 를 볼 수 있 습 니 다.http://zh.wikipedia.org/zh-cn/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84
아니면 이 블 로그:http://dongxicheng.org/structure/binary_indexed_tree/
이 물건 은 프로 그래 밍 의 아름다움 속 의 1.7 빛 과 그림자 절단 문 제 를 해결 할 수 있다.
 

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;
        }
    }
}