Fenwick Tree 기반 온라인 구간 합

외부 배열:
values[0..N)

내부 배열:
tree[1..N]

LSB(i)
= i & -i

tree[i]가 담당하는 범위:
(i - LSB(i), i]
1-based 기준

Point Add:
index의 조상 구간을 따라 delta 반영

Prefix Sum:
endExclusive에서 부모 구간을 따라 누적

Range Sum:
sum([start, end))
= prefix(end) - prefix(start)

복잡도:
Point Add   = O(log N)
Prefix Sum  = O(log N)
Range Sum   = O(log N)
Storage     = O(N)

Bucket 수:
1,440

입력:
- 현재 발생한 요청
- 지연 도착한 과거 요청
- 중복 제거 후의 음수 보정

조회:
- 09:00~10:00 요청 수
- 자정부터 현재까지 누적 요청 수
- 최근 15분 요청 수

prefix[minute]
= 자정부터 minute 전까지의 누적값

09:00~10:00
= prefix[600] - prefix[540]

values[497] += 1

그 뒤의 모든 prefix:
prefix[498..1440] += 1

add(497, +1)

rangeSum(540, 600)

외부 index:
0-based

구간:
[startInclusive, endExclusive)

prefixSum(endExclusive):
[0, endExclusive)의 합

#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <stdexcept>
#include <string>
#include <vector>

class FenwickTree final
{
public:
    explicit FenwickTree(std::size_t size)
        : size_(validatedSize(size)),
          tree_(size_ + 1, 0)
    {}

    FenwickTree(const FenwickTree&) = default;
    FenwickTree& operator=(const FenwickTree&) = default;

    FenwickTree(FenwickTree&&) noexcept = default;
    FenwickTree& operator=(FenwickTree&&) noexcept = default;

    void add(
        std::size_t index,
        std::int64_t delta)
    {
        validateIndex(index);

        std::array<
            std::size_t,
            std::numeric_limits<
                std::size_t>::digits> touched{};

        const std::size_t touchedCount =
            collectTouchedIndices(
                index,
                touched);

        validateUpdate(
            touched,
            touchedCount,
            delta);

        applyUpdate(
            touched,
            touchedCount,
            delta);
    }

    [[nodiscard]]
    std::int64_t prefixSum(
        std::size_t endExclusive) const
    {
        validateEnd(endExclusive, "endExclusive");

        std::int64_t result = 0;

        for (std::size_t index = endExclusive;
             index > 0;
             index -= leastSignificantBit(index))
        {
            result = checkedAdd(
                result,
                tree_[index]);
        }

        return result;
    }

    [[nodiscard]]
    std::int64_t rangeSum(
        std::size_t startInclusive,
        std::size_t endExclusive) const
    {
        validateRange(
            startInclusive,
            endExclusive);

        return checkedSubtract(
            prefixSum(endExclusive),
            prefixSum(startInclusive));
    }

    [[nodiscard]]
    std::int64_t getPointValue(
        std::size_t index) const
    {
        validateIndex(index);

        return rangeSum(
            index,
            index + 1);
    }

    [[nodiscard]]
    std::size_t getSize() const noexcept
    {
        return size_;
    }

private:
    static constexpr std::size_t maximumSize =
        10'000'000;

    std::size_t size_;
    std::vector<std::int64_t> tree_;

    [[nodiscard]]
    std::size_t collectTouchedIndices(
        std::size_t externalIndex,
        std::span<std::size_t> output) const
    {
        std::size_t count = 0;

        for (std::size_t index = externalIndex + 1;
             index <= size_;
             index += leastSignificantBit(index))
        {
            output[count] = index;
            count += 1;
        }

        return count;
    }

    void validateUpdate(
        std::span<const std::size_t> indices,
        std::size_t count,
        std::int64_t delta) const
    {
        for (std::size_t index = 0;
             index < count;
             index += 1)
        {
            ensureCanAdd(
                tree_[indices[index]],
                delta);
        }
    }

    void applyUpdate(
        std::span<const std::size_t> indices,
        std::size_t count,
        std::int64_t delta)
    {
        for (std::size_t index = 0;
             index < count;
             index += 1)
        {
            tree_[indices[index]] += delta;
        }
    }

    static std::size_t leastSignificantBit(
        std::size_t value) noexcept
    {
        return value & (~value + 1);
    }

    static void ensureCanAdd(
        std::int64_t left,
        std::int64_t right)
    {
        constexpr auto minimum =
            std::numeric_limits<std::int64_t>::min();

        constexpr auto maximum =
            std::numeric_limits<std::int64_t>::max();

        if (right > 0 && left > maximum - right)
        {
            throw std::overflow_error(
                "Fenwick Tree 합이 int64 범위를 초과합니다.");
        }

        if (right < 0 && left < minimum - right)
        {
            throw std::overflow_error(
                "Fenwick Tree 합이 int64 범위를 초과합니다.");
        }
    }

    static std::int64_t checkedAdd(
        std::int64_t left,
        std::int64_t right)
    {
        ensureCanAdd(left, right);
        return left + right;
    }

    static std::int64_t checkedSubtract(
        std::int64_t left,
        std::int64_t right)
    {
        constexpr auto minimum =
            std::numeric_limits<std::int64_t>::min();

        constexpr auto maximum =
            std::numeric_limits<std::int64_t>::max();

        if (right > 0 && left < minimum + right)
        {
            throw std::overflow_error(
                "구간 합이 int64 범위를 초과합니다.");
        }

        if (right < 0 && left > maximum + right)
        {
            throw std::overflow_error(
                "구간 합이 int64 범위를 초과합니다.");
        }

        return left - right;
    }

    void validateIndex(
        std::size_t index) const
    {
        if (index >= size_)
        {
            throw std::out_of_range(
                "index가 Fenwick Tree 범위를 벗어났습니다.");
        }
    }

    void validateEnd(
        std::size_t value,
        const char* name) const
    {
        if (value > size_)
        {
            throw std::out_of_range(
                std::string{name}
                + "가 범위를 벗어났습니다.");
        }
    }

    void validateRange(
        std::size_t startInclusive,
        std::size_t endExclusive) const
    {
        validateEnd(startInclusive, "startInclusive");
        validateEnd(endExclusive, "endExclusive");

        if (startInclusive > endExclusive)
        {
            throw std::out_of_range(
                "구간이 유효하지 않습니다.");
        }
    }

    [[nodiscard]]
    static std::size_t validatedSize(
        std::size_t size)
    {
        if (size == 0 || size > maximumSize)
        {
            throw std::invalid_argument(
                "size는 1 이상 10,000,000 이하이어야 합니다.");
        }

        return size;
    }
};

FenwickTree counts{1'440};

counts.add(497, 1);
counts.add(540, 3);
counts.add(599, 2);

const std::int64_t morning =
    counts.rangeSum(540, 600);

from __future__ import annotations


class FenwickTree:
    _MAXIMUM_SIZE = 10_000_000

    def __init__(self, size: int) -> None:
        _validate_size(
            size,
            self._MAXIMUM_SIZE,
        )

        self._size = size
        self._tree = [0] * (size + 1)

    def add(
        self,
        index: int,
        delta: int,
    ) -> None:
        self._validate_index(index)
        _validate_integer(delta, "delta")

        internal_index = index + 1

        while internal_index <= self._size:
            self._tree[internal_index] += delta

            internal_index += (
                _least_significant_bit(
                    internal_index
                )
            )

    def prefix_sum(
        self,
        end_exclusive: int,
    ) -> int:
        self._validate_end(
            end_exclusive,
            "end_exclusive",
        )

        result = 0
        internal_index = end_exclusive

        while internal_index > 0:
            result += self._tree[internal_index]

            internal_index -= (
                _least_significant_bit(
                    internal_index
                )
            )

        return result

    def range_sum(
        self,
        start_inclusive: int,
        end_exclusive: int,
    ) -> int:
        self._validate_range(
            start_inclusive,
            end_exclusive,
        )

        return (
            self.prefix_sum(end_exclusive)
            - self.prefix_sum(start_inclusive)
        )

    def get_point_value(self, index: int) -> int:
        self._validate_index(index)

        return self.range_sum(
            index,
            index + 1,
        )

    def get_size(self) -> int:
        return self._size

    def _validate_index(self, index: int) -> None:
        _validate_integer(index, "index")

        if index < 0 or index >= self._size:
            raise IndexError(
                "index가 Fenwick Tree 범위를 벗어났습니다."
            )

    def _validate_end(
        self,
        value: int,
        field_name: str,
    ) -> None:
        _validate_integer(value, field_name)

        if value < 0 or value > self._size:
            raise IndexError(
                f"{field_name}가 범위를 벗어났습니다."
            )

    def _validate_range(
        self,
        start_inclusive: int,
        end_exclusive: int,
    ) -> None:
        self._validate_end(
            start_inclusive,
            "start_inclusive",
        )
        self._validate_end(
            end_exclusive,
            "end_exclusive",
        )

        if start_inclusive > end_exclusive:
            raise ValueError(
                "start_inclusive는 "
                "end_exclusive보다 클 수 없습니다."
            )


def _least_significant_bit(
    value: int,
) -> int:
    return value & -value


def _validate_size(
    size: int,
    maximum_size: int,
) -> None:
    _validate_integer(size, "size")

    if size < 1 or size > maximum_size:
        raise ValueError(
            "size는 1 이상 "
            f"{maximum_size} 이하이어야 합니다."
        )


def _validate_integer(
    value: int,
    field_name: str,
) -> None:
    if (
        not isinstance(value, int)
        or isinstance(value, bool)
    ):
        raise TypeError(
            f"{field_name}는 정수여야 합니다."
        )

counts = FenwickTree(1_440)

counts.add(497, 1)
counts.add(540, 3)
counts.add(599, 2)

morning = counts.range_sum(
    540,
    600,
)

using System;

public sealed class FenwickTree
{
    private const int MaximumSize = 10_000_000;
    private const int MaximumTreeDepth = 64;

    private readonly long[] tree;
    private readonly int size;

    public FenwickTree(int size)
    {
        ValidateSize(size);

        this.size = size;
        this.tree = new long[size + 1];
    }

    public void Add(
        int index,
        long delta)
    {
        this.ValidateIndex(index);

        Span<int> touched =
            stackalloc int[MaximumTreeDepth];

        int touchedCount =
            this.CollectTouchedIndices(
                index,
                touched);

        this.ValidateUpdate(
            touched,
            touchedCount,
            delta);

        this.ApplyUpdate(
            touched,
            touchedCount,
            delta);
    }

    public long PrefixSum(
        int endExclusive)
    {
        this.ValidateEnd(
            endExclusive,
            nameof(endExclusive));

        long result = 0;

        for (
            int index = endExclusive;
            index > 0;
            index -= LeastSignificantBit(index))
        {
            result = checked(
                result + this.tree[index]);
        }

        return result;
    }

    public long RangeSum(
        int startInclusive,
        int endExclusive)
    {
        this.ValidateRange(
            startInclusive,
            endExclusive);

        return checked(
            this.PrefixSum(endExclusive)
            - this.PrefixSum(startInclusive));
    }

    public long GetPointValue(int index)
    {
        this.ValidateIndex(index);

        return this.RangeSum(
            index,
            index + 1);
    }

    public int GetSize()
    {
        return this.size;
    }

    private int CollectTouchedIndices(
        int externalIndex,
        Span<int> output)
    {
        int count = 0;

        for (
            int index = externalIndex + 1;
            index <= this.size;
            index += LeastSignificantBit(index))
        {
            output[count] = index;
            count += 1;
        }

        return count;
    }

    private void ValidateUpdate(
        ReadOnlySpan<int> indices,
        int count,
        long delta)
    {
        for (int index = 0; index < count; index += 1)
        {
            _ = checked(
                this.tree[indices[index]]
                + delta);
        }
    }

    private void ApplyUpdate(
        ReadOnlySpan<int> indices,
        int count,
        long delta)
    {
        for (int index = 0; index < count; index += 1)
        {
            this.tree[indices[index]] += delta;
        }
    }

    private static int LeastSignificantBit(
        int value)
    {
        return value & -value;
    }

    private void ValidateIndex(int index)
    {
        if (index < 0 || index >= this.size)
        {
            throw new ArgumentOutOfRangeException(
                nameof(index));
        }
    }

    private void ValidateEnd(
        int value,
        string parameterName)
    {
        if (value < 0 || value > this.size)
        {
            throw new ArgumentOutOfRangeException(
                parameterName);
        }
    }

    private void ValidateRange(
        int startInclusive,
        int endExclusive)
    {
        this.ValidateEnd(
            startInclusive,
            nameof(startInclusive));
        this.ValidateEnd(
            endExclusive,
            nameof(endExclusive));

        if (startInclusive > endExclusive)
        {
            throw new ArgumentOutOfRangeException(
                nameof(startInclusive));
        }
    }

    private static void ValidateSize(int size)
    {
        if (size is < 1 or > MaximumSize)
        {
            throw new ArgumentOutOfRangeException(
                nameof(size));
        }
    }
}

FenwickTree counts = new(1_440);

counts.Add(497, 1);
counts.Add(540, 3);
counts.Add(599, 2);

long morning =
    counts.RangeSum(540, 600);

export class FenwickTree
{
  static readonly #maximumSize =
    10_000_000;

  readonly #size: number;
  readonly #tree: bigint[];

  public static fromValues(
    values: readonly bigint[],
    signal?: AbortSignal,
  ): FenwickTree
  {
    if (values.length === 0) {
      throw new RangeError(
        "빈 배열에서는 Fenwick Tree를 만들 수 없습니다.",
      );
    }

    const result =
      new FenwickTree(values.length);

    for (
      let internalIndex = 1;
      internalIndex <= values.length;
      internalIndex += 1
    ) {
      signal?.throwIfAborted();

      const value =
        values[internalIndex - 1];

      validateBigInt(value, "value");

      result.#tree[internalIndex] += value;

      const parentIndex =
        internalIndex
        + leastSignificantBit(
            internalIndex);

      if (parentIndex <= values.length) {
        result.#tree[parentIndex] +=
          result.#tree[internalIndex];
      }
    }

    return result;
  }

  public constructor(size: number)
  {
    validateSize(
      size,
      FenwickTree.#maximumSize,
    );

    this.#size = size;
    this.#tree =
      new Array<bigint>(size + 1)
        .fill(0n);
  }

  public add(
    index: number,
    delta: bigint,
  ): void
  {
    this.#validateIndex(index);
    validateBigInt(delta, "delta");

    let internalIndex = index + 1;

    while (internalIndex <= this.#size) {
      this.#tree[internalIndex] += delta;

      internalIndex +=
        leastSignificantBit(internalIndex);
    }
  }

  public prefixSum(
    endExclusive: number,
  ): bigint
  {
    this.#validateEnd(
      endExclusive,
      "endExclusive",
    );

    let result = 0n;
    let internalIndex = endExclusive;

    while (internalIndex > 0) {
      result += this.#tree[internalIndex];

      internalIndex -=
        leastSignificantBit(internalIndex);
    }

    return result;
  }

  public rangeSum(
    startInclusive: number,
    endExclusive: number,
  ): bigint
  {
    this.#validateRange(
      startInclusive,
      endExclusive,
    );

    return this.prefixSum(endExclusive)
      - this.prefixSum(startInclusive);
  }

  public getPointValue(
    index: number,
  ): bigint
  {
    this.#validateIndex(index);

    return this.rangeSum(
      index,
      index + 1,
    );
  }

  public getSize(): number
  {
    return this.#size;
  }

  #validateIndex(index: number): void
  {
    validateInteger(index, "index");

    if (index < 0 || index >= this.#size) {
      throw new RangeError(
        "index가 Fenwick Tree 범위를 벗어났습니다.",
      );
    }
  }

  #validateEnd(
    value: number,
    fieldName: string,
  ): void
  {
    validateInteger(
      value,
      fieldName,
    );

    if (value < 0 || value > this.#size) {
      throw new RangeError(
        `${fieldName}가 범위를 벗어났습니다.`,
      );
    }
  }

  #validateRange(
    startInclusive: number,
    endExclusive: number,
  ): void
  {
    this.#validateEnd(
      startInclusive,
      "startInclusive",
    );
    this.#validateEnd(
      endExclusive,
      "endExclusive",
    );

    if (startInclusive > endExclusive) {
      throw new RangeError(
        "startInclusive는 "
        + "endExclusive보다 클 수 없습니다.",
      );
    }
  }
}

function leastSignificantBit(
  value: number,
): number
{
  return value & -value;
}

function validateSize(
  size: number,
  maximumSize: number,
): void
{
  validateInteger(size, "size");

  if (size < 1 || size > maximumSize) {
    throw new RangeError(
      "size는 1 이상 "
      + `${maximumSize} 이하이어야 합니다.`,
    );
  }
}

function validateInteger(
  value: number,
  fieldName: string,
): void
{
  if (!Number.isSafeInteger(value)) {
    throw new TypeError(
      `${fieldName}는 안전한 정수여야 합니다.`,
    );
  }
}

function validateBigInt(
  value: bigint,
  fieldName: string,
): void
{
  if (typeof value !== "bigint") {
    throw new TypeError(
      `${fieldName}는 bigint여야 합니다.`,
    );
  }
}

const counts =
  new FenwickTree(1_440);

counts.add(497, 1n);
counts.add(540, 3n);
counts.add(599, 2n);

const morning =
  counts.rangeSum(540, 600);

export type MinuteCountRepository = Readonly<{
  readDayAsync: (
    day: string,
    signal?: AbortSignal,
  ) => Promise<readonly bigint[]>;

  appendDeltaAsync: (
    day: string,
    minuteIndex: number,
    delta: bigint,
    signal?: AbortSignal,
  ) => Promise<void>;
}>;

const minuteCountPerDay = 1_440;

export class DailyTrafficIndex
{
  readonly #tree: FenwickTree;

  public constructor(
    tree = new FenwickTree(
      minuteCountPerDay,
    ),
  )
  {
    if (tree.getSize() !== minuteCountPerDay) {
      throw new RangeError(
        "일별 Fenwick Tree 크기가 유효하지 않습니다.",
      );
    }

    this.#tree = tree;
  }

  public recordDelta(
    minuteIndex: number,
    delta: bigint,
  ): void
  {
    this.#tree.add(
      minuteIndex,
      delta,
    );
  }

  public countRange(
    startMinute: number,
    endMinute: number,
  ): bigint
  {
    return this.#tree.rangeSum(
      startMinute,
      endMinute,
    );
  }

  public countUntil(
    endMinute: number,
  ): bigint
  {
    return this.#tree.prefixSum(
      endMinute,
    );
  }
}

export async function rebuildDailyIndexAsync(
  repository: MinuteCountRepository,
  day: string,
  signal?: AbortSignal,
): Promise<DailyTrafficIndex>
{
  validateDay(day);

  const counts =
    await repository.readDayAsync(
      day,
      signal,
    );

  if (counts.length !== minuteCountPerDay) {
    throw new RangeError(
      "일별 count snapshot 크기가 유효하지 않습니다.",
    );
  }

  signal?.throwIfAborted();

  return new DailyTrafficIndex(
    FenwickTree.fromValues(
      counts,
      signal,
    ),
  );
}

export async function recordDeltaDurablyAsync(
  repository: MinuteCountRepository,
  index: DailyTrafficIndex,
  day: string,
  minuteIndex: number,
  delta: bigint,
  signal?: AbortSignal,
): Promise<void>
{
  validateDay(day);

  await repository.appendDeltaAsync(
    day,
    minuteIndex,
    delta,
    signal,
  );

  index.recordDelta(
    minuteIndex,
    delta,
  );
}

function validateDay(day: string): void
{
  if (!/^\d{4}-\d{2}-\d{2}$/.test(day)) {
    throw new RangeError(
      "day는 YYYY-MM-DD 형식이어야 합니다.",
    );
  }
}

Timestamp Boundary
= UTC 또는 업무 timezone 결정
= timestamp → minute index 변환

MinuteCountRepository
= 원본 event·delta의 영속성
= 재시작 복구용 snapshot 제공

DailyTrafficIndex
= point delta와 구간 합
= 외부 I/O 없음

Query Service
= 사용자 시간 범위를 minute range로 변환

Central Policy Handler
= repository 장애
= cancellation
= snapshot 불일치 처리

외부 index가 0-based인가
→ 내부 배열이 1-based인가
→ index 0을 내부 update loop에 직접 넣지 않는가
→ tree[i]가 어떤 구간을 담당하는가
→ update가 i += LSB(i)로 이동하는가
→ query가 i -= LSB(i)로 이동하는가
→ prefix range가 [0, end)인가
→ range가 [start, end)인가
→ 빈 range가 0을 반환하는가
→ overflow 실패 시 부분 mutation이 남지 않는가
→ 동시 update/query 정책이 명시되어 있는가

tree[i]
=
values[
  i - LSB(i)
  ...
  i - 1
]

외부 0-based,
내부 1-based 기준

i = 0

LSB(0)
= 0

0 += LSB(0)
0 += 0

- 하루 1,440개 minute bucket
- 상품 category 0..N-1
- 압축된 좌표
- 고정된 histogram bucket

- 임의 UUID
- 중간 index 삽입
- 동적으로 계속 늘어나는 정렬 key

rangeSum(start, end)
=
prefix(end) - prefix(start)

외부 입력
  ↓
validateRange
  ↓ Result<ValidatedRange, FenwickFailure>
호출부가 실패를 처리
  ↓
검증된 range 묶음
  ↓
rangeSumUnchecked
  ↓ bigint, long, int64_t
반복 계산

  // FenwickTree 내부. ValidatedRange를 통과한 값만 받는다.
  #rangeSumUnchecked(
    startInclusive: number,
    endExclusive: number,
  ): bigint
  {
    return this.prefixSum(endExclusive)
      - this.prefixSum(startInclusive);
  }

  public sumValidatedBatch(
    ranges: readonly ValidatedRange[],
  ): bigint[]
  {
    return ranges.map((range) =>
      this.#rangeSumUnchecked(
        range.startInclusive,
        range.endExclusive,
      ));
  }

type Result<T, E> =
  | Readonly<{ ok: true; value: T }>
  | Readonly<{ ok: false; error: E }>;

type FenwickFailure =
  | Readonly<{ code: "invalid-size"; size: number }>
  | Readonly<{
      code: "invalid-range";
      startInclusive: number;
      endExclusive: number;
      size: number;
    }>;

type ValidatedRange = Readonly<{
  startInclusive: number;
  endExclusive: number;
}>;

const maximumSize = 10_000_000;

function validateRange(
  size: number,
  startInclusive: number,
  endExclusive: number,
): Result<ValidatedRange, FenwickFailure>
{
  if (
    !Number.isSafeInteger(size)
    || size < 1
    || size > maximumSize
  ) {
    return {
      ok: false,
      error: { code: "invalid-size", size },
    };
  }

  if (
    !Number.isSafeInteger(startInclusive)
    || !Number.isSafeInteger(endExclusive)
    || startInclusive < 0
    || startInclusive > endExclusive
    || endExclusive > size
  ) {
    return {
      ok: false,
      error: {
        code: "invalid-range",
        startInclusive,
        endExclusive,
        size,
      },
    };
  }

  return {
    ok: true,
    value: { startInclusive, endExclusive },
  };
}

중복 event 취소:
add(minute, -1)

데이터:
초기 한 번 생성

Update:
없음

Query:
수백만 회

Build:
O(N)

Range Query:
O(1)

update 5:
6 → 8 → 16 → 32 ...

query 27:
27 → 26 → 24 → 16 ...

tree[6] 수정
tree[8] 수정
tree[16] 수정

- 단일 owner actor
- read/write lock
- update batch 후 immutable snapshot 교체
- shard별 독립 tree
- 원자적 node update와 허용 가능한 약한 일관성

node 1 수정 성공
node 2 수정 성공
node 3에서 overflow 예외

결과:
일부 node만 갱신
→ 내부 불변식 손상

- 업데이트 전 전체 node overflow 사전 검증
- 더 넓은 정수 형식
- saturation 정책
- modulo arithmetic을 명시한 domain

Source of truth:
event log, DB, durable snapshot

Derived index:
Fenwick Tree

- 내부 index를 0부터 시작해 무한 루프 발생
- Inclusive와 exclusive range를 혼용함
- size보다 큰 end를 조용히 clamp함
- 음수 index가 언어별로 다른 동작을 함
- overflow 후 일부 tree node만 수정됨
- Min query를 prefix subtraction으로 구현함
- 여러 thread가 synchronization 없이 update함
- process-local tree를 source of truth로 사용함
- 희소한 64-bit key에 거대한 배열을 할당함
- update가 없는 데이터에도 Fenwick Tree를 사용함

class FenwickTreeBad
{
  readonly #tree: number[];

  public constructor(size: number)
  {
    this.#tree =
      new Array<number>(size).fill(0);
  }

  public add(
    index: number,
    delta: number,
  ): void
  {
    while (index < this.#tree.length) {
      this.#tree[index] += delta;
      index += index & -index;
    }
  }
}

index = 0

index & -index
= 0

다음 index
= 0 + 0
= 0

- 입력 validation이 없다.
- NaN과 Infinity를 허용한다.
- 누적 합이 Number.MAX_SAFE_INTEGER를 넘을 수 있다.
- 내부 배열 길이와 valid index 규칙이 불명확하다.
- range의 inclusive/exclusive 의미가 없다.

externalIndex = 0

internalIndex
= externalIndex + 1
= 1

LSB(1)
= 1

다음:
1 → 2 → 4 → 8

tree[i]에 values[i-1] 반영
→ parent = i + LSB(i)
→ tree[parent] += tree[i]

import assert from "node:assert/strict";
import test from "node:test";

import { FenwickTree } from "./fenwick-tree.js";

test("Fenwick Tree는 기준 배열의 구간 합과 같다", () =>
{
  const size = 512;
  const tree = new FenwickTree(size);
  const reference =
    new Array<bigint>(size).fill(0n);

  const random =
    createDeterministicRandom(0x5eed);

  for (
    let step = 0;
    step < 50_000;
    step += 1
  ) {
    const operation =
      random() % 2;

    if (operation === 0) {
      const index =
        random() % size;

      const delta =
        BigInt(
          (random() % 201) - 100);

      tree.add(index, delta);
      reference[index] += delta;

      continue;
    }

    const first =
      random() % (size + 1);

    const second =
      random() % (size + 1);

    const start = Math.min(
      first,
      second,
    );

    const end = Math.max(
      first,
      second,
    );

    assert.equal(
      tree.rangeSum(start, end),
      sumReference(
        reference,
        start,
        end),
    );
  }
});

test("빈 구간의 합은 0이다", () =>
{
  const tree = new FenwickTree(10);

  tree.add(5, 100n);

  assert.equal(
    tree.rangeSum(5, 5),
    0n,
  );
});

test("첫 index와 마지막 index를 처리한다", () =>
{
  const tree = new FenwickTree(10);

  tree.add(0, 3n);
  tree.add(9, 7n);

  assert.equal(
    tree.rangeSum(0, 1),
    3n,
  );

  assert.equal(
    tree.rangeSum(9, 10),
    7n,
  );

  assert.equal(
    tree.rangeSum(0, 10),
    10n,
  );
});

function sumReference(
  values: readonly bigint[],
  start: number,
  end: number,
): bigint
{
  let result = 0n;

  for (
    let index = start;
    index < end;
    index += 1
  ) {
    result += values[index];
  }

  return result;
}

function createDeterministicRandom(
  seed: number,
): () => number
{
  let state = seed >>> 0;

  return () =>
  {
    state = (
      Math.imul(state, 1_664_525)
      + 1_013_904_223
    ) >>> 0;

    return state >>> 16;
  };
}

- size 0, 최대 size 초과
- 음수 index, size와 같은 point index
- startInclusive > endExclusive, endExclusive > size
- 빈 구간, 첫 index, 마지막 index, 전체 구간
- C++와 C#의 overflow 사전 검증 후 내부 배열이 변하지 않는지
- TypeScript fromValues의 빈 배열 거부와 O(N) build 결과
- rebuild의 정상 snapshot과 길이가 잘못된 snapshot

prefixSum(0) = 0

rangeSum(i, i) = 0

rangeSum(i, i+1)
= getPointValue(i)

rangeSum(0, N)
= 모든 point의 합

add(i, d) 후:
i를 포함하는 range만 d만큼 변함

Raw Array:
Update O(1)
Query O(range length)

Prefix Array:
Update O(N)
Query O(1)

Fenwick Tree:
Update O(log N)
Query O(log N)

- N
- Update:Query 비율
- Query range 길이 분포
- Random/clustered index 분포
- Thread 수
- Integer width
- 초기 build 빈도

fenwick.update.count
fenwick.query.count
fenwick.update.duration_ns
fenwick.query.duration_ns
fenwick.rebuild.count
fenwick.rebuild.duration_ms
fenwick.size
fenwick.overflow.count

- number보다 산술 비용이 클 수 있음
- JSON.stringify가 bigint를 직접 처리하지 못함
- number와 혼합 연산 불가

Public:
0-based

Prefix:
[0, endExclusive)

Range:
[startInclusive, endExclusive)

Internal:
1-based

LSB:
positive index에서만 계산

한 값만 바뀌는데 누적합 전체를 다시 쓰지 마라.

각 index가 담당하는 이진 구간만 갱신하고,
prefix 두 개의 차이로 원하는 구간을 계산하라.