0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Karentia

TypeScriptでFenwick Treeを実装する：一点更新と区間和をO(log n)にする

0
Posted at

Fenwick Treeの区間と更新・集計パス

原文の背景メモ: https://www.aceround.app/ja/blog/ai-coding-interview-assistant

Fenwick Tree（Binary Indexed Tree / BIT）は、配列への一点更新と区間和が混在するときに使えるデータ構造です。どちらも $O(\log n)$ で処理でき、Segment Treeより実装が短いため、技術面接でも説明しやすい選択肢です。

この記事では、外側を0-based・半開区間 [left, right) に統一したTypeScript実装を作ります。内部だけ1-basedに変換し、i & -i が表す区間、不変条件、境界テストまで確認します。

先に結論

配列の一点更新と区間和に必要な計算量は次の通りです。

方法 一点更新 区間和
素朴な配列 $O(1)$ $O(n)$
累積和 $O(n)$ $O(1)$
Fenwick Tree $O(\log n)$ $O(\log n)$

Fenwick Treeは万能ではありません。最大値や最小値など、差分で区間を戻せない演算にはSegment Treeの方が向いています。一方、加算・頻度・個数・転倒数のような「prefixの差で区間を求められる」問題にはよく合います。

tree[i] が持つ区間

Fenwick Treeの内部配列は1-basedで扱います。tree[i] が担当する要素数は、i の最下位の1bitです。

const lowbit = (i: number): number => i & -i;

たとえば i = 6 は2進数で 110 なので、lowbit(6) = 2 です。したがって tree[6] は末尾が6、長さが2の区間 [5..6] を持ちます。

i 2進数 lowbit(i) tree[i] の担当区間
1 001 1 [1..1]
2 010 2 [1..2]
3 011 1 [3..3]
4 100 4 [1..4]
5 101 1 [5..5]
6 110 2 [5..6]
7 111 1 [7..7]
8 1000 8 [1..8]

この区間分割から、2つの移動規則が出ます。

  • prefixを集計するとき: i -= i & -i
  • 一点更新を伝播するとき: i += i & -i

prefixSum(7) は [1..7] を [7] + [5..6] + [1..4] に重複なく分解しています。更新側は、対象要素を含む上位区間だけをたどります。どちらも添字のbitが1つずつ変化するため、反復回数は $O(\log n)$ です。

TypeScript実装

公開APIは通常の配列と同じ0-basedにし、区間は [left, right) に統一します。prefixSum(endExclusive) は先頭から endExclusive 未満までの和です。

export class FenwickTree {
  private readonly tree: number[];
  private readonly values: number[];

  constructor(values: readonly number[]) {
    if (!values.every(Number.isFinite)) {
      throw new TypeError('values must contain only finite numbers');
    }

    this.values = [...values];
    this.tree = new Array(values.length + 1).fill(0);

    // 完成した各ノードを親へ足すとO(n)で構築できます。
    for (let i = 1; i <= values.length; i += 1) {
      this.tree[i] += values[i - 1];
      const parent = i + (i & -i);
      if (parent <= values.length) {
        this.tree[parent] += this.tree[i];
      }
    }
  }

  get length(): number {
    return this.values.length;
  }

  add(index: number, delta: number): void {
    this.assertIndex(index);
    if (!Number.isFinite(delta)) {
      throw new TypeError('delta must be a finite number');
    }

    this.values[index] += delta;

    for (let i = index + 1; i <= this.length; i += i & -i) {
      this.tree[i] += delta;
    }
  }

  set(index: number, value: number): void {
    this.assertIndex(index);
    if (!Number.isFinite(value)) {
      throw new TypeError('value must be a finite number');
    }

    this.add(index, value - this.values[index]);
  }

  prefixSum(endExclusive: number): number {
    this.assertBoundary(endExclusive);

    let sum = 0;
    for (let i = endExclusive; i > 0; i -= i & -i) {
      sum += this.tree[i];
    }
    return sum;
  }

  rangeSum(left: number, right: number): number {
    this.assertBoundary(left);
    this.assertBoundary(right);
    if (left > right) {
      throw new RangeError('left must be less than or equal to right');
    }

    return this.prefixSum(right) - this.prefixSum(left);
  }

  private assertIndex(index: number): void {
    if (!Number.isInteger(index) || index < 0 || index >= this.length) {
      throw new RangeError(`index must be an integer in [0, ${this.length})`);
    }
  }

  private assertBoundary(index: number): void {
    if (!Number.isInteger(index) || index < 0 || index > this.length) {
      throw new RangeError(`boundary must be an integer in [0, ${this.length}]`);
    }
  }
}

なぜ values も保持するのか

Fenwick Treeが直接扱うのは「値そのもの」ではなく差分です。add(index, delta) だけなら tree で足りますが、set(index, value) を提供するには現在値との差を求める必要があります。

delta = value - currentValue;

そのため、この実装では元配列のコピーも保持しています。メモリを最小化したい場合は set を外し、呼び出し側が差分だけを渡す設計でも構いません。

Bunで境界をテストする

代表例だけでは、0-basedと1-basedの変換ミスや右端のoff-by-oneを見逃します。固定ケースに加えて、素朴な配列とのランダム差分テストを入れます。

import { describe, expect, test } from 'bun:test';
import { FenwickTree } from './fenwick-tree';

describe('FenwickTree', () => {
  test('returns prefix and half-open range sums', () => {
    const bit = new FenwickTree([2, 1, 3, 5, 4]);

    expect(bit.prefixSum(0)).toBe(0);
    expect(bit.prefixSum(3)).toBe(6);
    expect(bit.rangeSum(1, 4)).toBe(9);
    expect(bit.rangeSum(2, 2)).toBe(0);
  });

  test('supports delta updates and assignment updates', () => {
    const bit = new FenwickTree([2, 1, 3, 5, 4]);

    bit.add(2, 4);
    expect(bit.rangeSum(0, 3)).toBe(10);

    bit.set(3, 1);
    expect(bit.rangeSum(2, 5)).toBe(12);
  });

  test('rejects invalid indices and ranges', () => {
    const bit = new FenwickTree([1, 2, 3]);

    expect(() => bit.add(-1, 1)).toThrow(RangeError);
    expect(() => bit.add(3, 1)).toThrow(RangeError);
    expect(() => bit.rangeSum(2, 1)).toThrow(RangeError);
    expect(() => bit.prefixSum(4)).toThrow(RangeError);
  });

  test('matches a naive array under random operations', () => {
    let seed = 0x12345678;
    const random = (): number => {
      seed = (1664525 * seed + 1013904223) >>> 0;
      return seed / 0x1_0000_0000;
    };

    const values = new Array<number>(32).fill(0);
    const bit = new FenwickTree(values);

    for (let step = 0; step < 500; step += 1) {
      const index = Math.floor(random() * values.length);
      const delta = Math.floor(random() * 21) - 10;
      values[index] += delta;
      bit.add(index, delta);

      const a = Math.floor(random() * (values.length + 1));
      const b = Math.floor(random() * (values.length + 1));
      const left = Math.min(a, b);
      const right = Math.max(a, b);
      const expected = values
        .slice(left, right)
        .reduce((sum, value) => sum + value, 0);

      expect(bit.rangeSum(left, right)).toBe(expected);
    }
  });
});

実行コマンドです。

bun test fenwick-tree.test.ts

面接で説明する順番

ライブコーディングでは、いきなり i & -i から話すと意図が伝わりにくくなります。次の順番だと設計判断を説明しやすいです。

  1. 一点更新と区間和が混在し、配列や固定の累積和では片方が $O(n)$ になると整理します。
  2. 区間和を prefix(right) - prefix(left) に分解します。
  3. prefixを2のべき乗サイズの区間に分解して保持すると説明します。
  4. lowbit(i) = i & -i で担当区間の長さを求めます。
  5. 外部APIは0-based、内部だけ1-basedという境界を明示します。
  6. 最後に空区間、配列末尾、不正index、ランダム差分テストを確認します。

特に重要な不変条件は、tree[i] が常に次の区間和を持つことです。

[i - lowbit(i) + 1, i]

add はこの区間に対象indexを含むノードだけを上へ更新し、prefixSum は互いに重ならない担当区間を右から集めます。この不変条件まで説明できれば、コードを暗記しているだけではなく、なぜ動くかを理解していることが伝わります。

まとめ

  • 一点更新とprefix sumはどちらも $O(\log n)$ です。
  • 区間和は2つのprefix sumの差で求めます。
  • 外側を0-based・半開区間、内側を1-basedに分離すると境界が安定します。
  • tree[i] の担当区間 [i - lowbit(i) + 1, i] が中心の不変条件です。
  • 固定例だけでなく、素朴解とのランダム差分テストがoff-by-oneの検出に効きます。

Segment Treeほど汎用ではありませんが、加算系の更新と区間集計に限れば、Fenwick Treeは短く、速く、説明もしやすい実装です。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?