Binary Indexed Tree

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(log n)	O(log n)	O(log n)	O(log n)

Definition

Short

Binary Indexed Tree is a data structure that allows efficient updates and range queries on an array. It is built by storing the cumulative sums of the array elements in a binary tree, allowing for efficient computation of prefix sums and range queries.

Simplified

It's like a smart organizer at a party. It quickly updates or calculates the total of a series of numbers (like candies held by people), saving a lot of time.

Detailed

Binary Indexed Tree (Fenwick Tree), is a data structure that efficiently updates elements and calculates prefix sums in a number table.

Unlike a flat array, a Fenwick tree balances 2 operations:

• element update
• prefix sum calculation

In a flat array of n numbers, storing elements allows constant time operations but requires linear time for prefix sums. Storing prefix sums allows constant time operations but requires linear time for element updates.

Fenwick trees overcome this by allowing both operations in O(log n) time. This is achieved by representing the numbers as a tree, where each node's value is the sum of the numbers in its subtree.

Practice

Practice

Aspect	Pseudo Code
Increase	increase(position, value): if position < 1 or position > tree_array.length: 'Position is out of allowed range' for i in range(position, tree_array.length + 1, i & -i): tree_array[i] += value
Query	query(position): if position < 1 or position > tree_array.length: 'Position is out of allowed range' sum = 0 for i in range(position, 0, -(i & -i)): sum += tree_array[i] return sum
Query Range	query_range(left_index, right_index): if left_index > right_index: 'Left index cannot be greater than right one' if left_index == 1: return query(right_index) return query(right_index) - query(left_index - 1) query(position): if position < 1 or position > tree_array.length: 'Position is out of allowed range' sum = 0 for i in range(position, 0, -(i & -i)): sum += tree_array[i] return sum

Solution

package main

import (
	"errors"
)

type FenwickTree struct {
	arraySize int
	treeArray []int
}

func NewFenwickTree(arraySize int) *FenwickTree {
	treeArray := make([]int, arraySize+1)
	return &FenwickTree{arraySize: arraySize, treeArray: treeArray}
}

func (f *FenwickTree) Increase(position, value int) error {
	if position < 1 || position > f.arraySize {
		return errors.New("Position is out of allowed range")
	}

	for i := position; i <= f.arraySize; i += i & -i {
		f.treeArray[i] += value
	}

	return nil
}

func (f *FenwickTree) Query(position int) (int, error) {
	if position < 1 || position > f.arraySize {
		return 0, errors.New("Position is out of allowed range")
	}

	sum := 0

	for i := position; i > 0; i -= i & -i {
		sum += f.treeArray[i]
	}

	return sum, nil
}

func (f *FenwickTree) QueryRange(leftIndex, rightIndex int) (int, error) {
	if leftIndex > rightIndex {
		return 0, errors.New("Left index cannot be greater than right one")
	}

	if leftIndex == 1 {
		return f.Query(rightIndex)
	}

	return f.Query(rightIndex) - f.Query(leftIndex-1), nil
}

public class FenwickTree {

  private int arraySize;
  private int[] treeArray;

  public FenwickTree(int arraySize) {
    this.arraySize = arraySize;
    this.treeArray = new int[arraySize + 1];
  }

  public FenwickTree increase(int position, int value) {
    if (position < 1 || position > arraySize) {
      throw new IllegalArgumentException("Position is out of allowed range");
    }

    for (int i = position; i <= arraySize; i += (i & -i)) {
      treeArray[i] += value;
    }

    return this;
  }

  public int query(int position) {
    if (position < 1 || position > arraySize) {
      throw new IllegalArgumentException("Position is out of allowed range");
    }

    int sum = 0;

    for (int i = position; i > 0; i -= (i & -i)) {
      sum += treeArray[i];
    }

    return sum;
  }

  public int queryRange(int leftIndex, int rightIndex) {
    if (leftIndex > rightIndex) {
      throw new IllegalArgumentException("Left index can not be greater than right one");
    }

    if (leftIndex == 1) {
      return query(rightIndex);
    }

    return query(rightIndex) - query(leftIndex - 1);
  }
}

class BinaryIndexedTree {
  constructor(arraySize) {
    this.arraySize = arraySize;
    this.treeArray = Array(this.arraySize + 1).fill(0);
  }

  increase(position, value) {
    if (position < 1 || position > this.arraySize) {
      throw new Error("Position is out of allowed range");
    }

    for (let i = position; i <= this.arraySize; i += i & -i) {
      this.treeArray[i] += value;
    }

    return this;
  }

  query(position) {
    if (position < 1 || position > this.arraySize) {
      throw new Error("Position is out of allowed range");
    }

    let sum = 0;

    for (let i = position; i > 0; i -= i & -i) {
      sum += this.treeArray[i];
    }

    return sum;
  }

  queryRange(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) {
      throw new Error("Left index can not be greater than right one");
    }

    if (leftIndex === 1) {
      return this.query(rightIndex);
    }

    return this.query(rightIndex) - this.query(leftIndex - 1);
  }
}

class FenwickTree(private val arraySize: Int) {
    private val treeArray = IntArray(arraySize + 1)

    fun increase(position: Int, value: Int): FenwickTree {
        if (position < 1 || position > arraySize) {
            throw IllegalArgumentException("Position is out of allowed range")
        }

        var i = position
        while (i <= arraySize) {
            treeArray[i] += value
            i += i and -i
        }

        return this
    }

    fun query(position: Int): Int {
        if (position < 1 || position > arraySize) {
            throw IllegalArgumentException("Position is out of allowed range")
        }

        var sum = 0
        var i = position

        while (i > 0) {
            sum += treeArray[i]
            i -= i and -i
        }

        return sum
    }

    fun queryRange(leftIndex: Int, rightIndex: Int): Int {
        if (leftIndex > rightIndex) {
            throw IllegalArgumentException("Left index can not be greater than right one")
        }

        return if (leftIndex == 1) {
            query(rightIndex)
        } else {
            query(rightIndex) - query(leftIndex - 1)
        }
    }
}

class FenwickTree:
    def __init__(self, array_size):
        self.array_size = array_size
        self.tree_array = [0] * (array_size + 1)

    def increase(self, position, value):
        if position < 1 or position > self.array_size:
            raise ValueError('Position is out of allowed range')

        i = position
        while i <= self.array_size:
            self.tree_array[i] += value
            i += i & -i

        return self

    def query(self, position):
        if position < 1 or position > self.array_size:
            raise ValueError('Position is out of allowed range')

        total_sum = 0
        i = position

        while i > 0:
            total_sum += self.tree_array[i]
            i -= i & -i

        return total_sum

    def query_range(self, left_index, right_index):
        if left_index > right_index:
            raise ValueError('Left index can not be greater than right one')

        if left_index == 1:
            return self.query(right_index)

        return self.query(right_index) - self.query(left_index - 1)

struct FenwickTree {
    array_size: usize,
    tree_array: Vec<i32>,
}

impl FenwickTree {
    fn new(array_size: usize) -> FenwickTree {
        FenwickTree {
            array_size,
            tree_array: vec![0; array_size + 1],
        }
    }

    fn increase(&mut self, position: usize, value: i32) -> Result<(), &'static str> {
        if position < 1 || position > self.array_size {
            return Err("Position is out of allowed range");
        }

        let mut i = position;
        while i <= self.array_size {
            self.tree_array[i] += value;
            i += i & i.wrapping_neg();
        }

        Ok(())
    }

    fn query(&self, position: usize) -> Result<i32, &'static str> {
        if position < 1 || position > self.array_size {
            return Err("Position is out of allowed range");
        }

        let mut sum = 0;
        let mut i = position;

        while i > 0 {
            sum += self.tree_array[i];
            i -= i & i.wrapping_neg();
        }

        Ok(sum)
    }

    fn query_range(&self, left_index: usize, right_index: usize) -> Result<i32, &'static str> {
        if left_index > right_index {
            return Err("Left index can not be greater than right one");
        }

        if left_index == 1 {
            return self.query(right_index);
        }

        Ok(self.query(right_index)? - self.query(left_index - 1)?)
    }
}

export default class FenwickTree {
  private arraySize: number;
  private treeArray: number[];

  constructor(arraySize: number) {
    this.arraySize = arraySize;
    this.treeArray = Array(this.arraySize + 1).fill(0);
  }

  increase(position: number, value: number): FenwickTree {
    if (position < 1 || position > this.arraySize) {
      throw new Error("Position is out of allowed range");
    }

    for (let i = position; i <= this.arraySize; i += i & -i) {
      this.treeArray[i] += value;
    }

    return this;
  }

  query(position: number): number {
    if (position < 1 || position > this.arraySize) {
      throw new Error("Position is out of allowed range");
    }

    let sum = 0;

    for (let i = position; i > 0; i -= i & -i) {
      sum += this.treeArray[i];
    }

    return sum;
  }

  queryRange(leftIndex: number, rightIndex: number): number {
    if (leftIndex > rightIndex) {
      throw new Error("Left index can not be greater than right one");
    }

    if (leftIndex === 1) {
      return this.query(rightIndex);
    }

    return this.query(rightIndex) - this.query(leftIndex - 1);
  }
}