フェニック木
実装例

C言語による単純な実装を紹介する。単なる数列に比べ、前処理は20%ほど長くなる。しかし、この実装のように非常に大きな数列を用いる場合にはその後の操作（要素の更新と部分和の計算）が約1600倍の速度で可能となる。
下の実装では他の手法との比較を含む。
/*******************************************************************/
/* This program demonstrates the speedup for a Fenwick tree vs a        */
/* flat array for performing multiple prefix sums.  It generates a             */
/* sequence of random numbers, then performs 1000 summations,      */
/* each of which starts and ends at random indices.                                  */
/*******************************************************************/
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

// Number of elements in the array
#define N (4*1024*1024)		// Elements in the array
#define COUNTS 1024		// Size of values stored
typedef unsigned long sum_t;	// Should be able to hold N * (COUNTS - 1)

// Number of queries to perform
#define NQUERIES 1000

// Isolate the least significant 1 bit.  E.g. LSB(0x1234) == 4.
#define LSB(i) ((i) & -(i))

// Fen_sum: return the sum of the first i elements, 0 through i-1.
sum_t Fen_sum(sum_t const *a, unsigned int i) 
{
	sum_t sum = 0;
	while (i) {
		sum += a[i-1];
		i -= LSB(i);
	}
	return sum;
}

// Fen_add: add k to element i (and thus Fen_sum(a, j) for all j > i)
void Fen_add(sum_t *a, unsigned int size, sum_t delta, unsigned int i) 
{
	while (i < size) {
		a[i] += delta;
		i += LSB(i+1);
	}
}

// Fen_range: Returns the sum of the elements [i..j-1]
// This could be written as "Fen_sum(a, j) - Fen_sum(a, i)",
// but it is possible to do it in less time (particularly for
// small ranges) by avoiding the terms that the two sums have
// in common.
sum_t Fen_range(sum_t const *a, unsigned int i, unsigned int j)
{
	sum_t sum = 0;

	while (j > i) {
		sum += a[j-1];
		j -= LSB(j);
	}

	while (i > j) {
		sum -= a[i-1];
		i -= LSB(i);
	}
	return sum;
}

// Fen_get: Returns the value of the element at index i
// (The time is proportional to the number of trailing 1 bits
// in i.  So even numbers are fast, and i = 0xffff takes 16 steps.)
sum_t Fen_get(sum_t const *a, unsigned int i)
{
	return Fen_range(a, i, i+1);
}

// Fen_set: sets the value of the element at index i
void Fen_set(sum_t *a, unsigned int size, sum_t value, unsigned int i)
{
	Fen_add(a, size, value - Fen_get(a, i), i);
}

// It's possible to initialize a Fenwick tree using Fen_add or
// Fen_set (you can even do the latter in-place if you go backward
// through the array), but for bulk initialization, this is faster.
void Fen_init(sum_t *a, unsigned int size)
{
	for (unsigned int i = 0; i < size; i++) {
		unsigned int j = i + LSB(i+1);
		if (j < size)
			a[j] += a[i];
	}
}

// main: allocates an array of numbers and fills it with a sequence of
// random numbers, then performs a series of summations (queries).  It
// then repeats the process using a Fenwick tree rather than a flat
// array.  The sequence of random numbers and the bounds of each query
// are identical for the flat array and the Fenwick tree.  The time
// required to populate the data structure and the total time required
// for all queries is calculated and reported for the flat array and
// for the Fenwick tree.

int main(void)
{
	sum_t *a;
	unsigned int queries[NQUERIES*2];
	clock_t time1, time2, time3;
	time_t seed = time(NULL);

	// generate the bounds for all of the queries
	srandom(seed + 1);
	for (unsigned int i = 0; i < NQUERIES * 2; i += 2) {
		unsigned int q = random() % N, r = random() % N;
		bool reverse = q > r;

		queries[i +  reverse] = q;
		queries[i + !reverse] = r;
	}

	// allocate the array of sums
	a = malloc(N * sizeof *a);

	// The following loop forces all pages into memory (otherwise the
	// timing of the algorithm could include a lot of page faults)
	for (unsigned int i = 0; i < N; i++)
		a[i] = 0;

	/*****************************************************************/
	/*   FLAT ARRAY METHOD                                           */
	/*****************************************************************/

	time1 = clock();
	// Store random numbers in a flat array
	srandom(seed);
	for (unsigned int i = 0; i < N; i++)
		a[i] = random() % COUNTS;
	time2 = clock();	// time2 - time1 = time for setup
	// perform the queries
	for (unsigned int j = 0; j < NQUERIES * 2; j += 2) {
		sum_t asum = 0;
		for (unsigned int i = queries[j]; i < queries[j+1]; i++)
			asum += a[i];
		printf(" %lu", asum);
	}
	time3 = clock();	// time3 - time2 = time for queries

	printf("\nFlat Array:\n Build: %f\n Query: %f\n",
		(time2-time1)*(1.0/CLOCKS_PER_SEC),
		(time3-time2)*(1.0/CLOCKS_PER_SEC));

	/*****************************************************************/
	/*   FENWICK TREE METHOD                                         */
	/*****************************************************************/

	time1 = clock();
	// Store the same random numbers in a Fenwick tree
	srandom(seed);
	for (unsigned int i = 0; i < N; i++)
		a[i] = random() % COUNTS;
	Fen_init(a, N);
	time2 = clock();	// time2 - time1 = time for setup
	// perform the queries
	for (unsigned int j = 0; j < NQUERIES * 2; j += 2)
		printf(" %lu", Fen_range(a, queries[j], queries[j+1]));
	time3 = clock();	// time3 - time2 = time for queries

	printf("\nFenwick:\n Build: %f\n Query: %f\n",
		(time2-time1)*(1.0/CLOCKS_PER_SEC),
		(time3-time2)*(1.0/CLOCKS_PER_SEC));

	free(a);
	return 0;
}