Fenwick Tree · Embed | Leonardo Wajda

    
  

  


  


  


  

class FenwickTree {
    int[] tree;

    FenwickTree(int n) {
        tree = new int[n + 1];
    }

    void add(int index, int delta) {
        for (index++; index < tree.length; index += index & -index) tree[index] += delta;
    }

    int sum(int index) {
        int total = 0;
        for (index++; index > 0; index -= index & -index) total += tree[index];
        return total;
    }
}
class FenwickTree:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        index += 1
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index

    def sum(self, index: int) -> int:
        total = 0
        index += 1
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total
final class FenwickTree(n: Int):
  private val tree = Array.fill(n + 1)(0)

  def add(index0: Int, delta: Int): Unit =
    var index = index0 + 1
    while index < tree.length do
      tree(index) += delta
      index += index & -index

  def sum(index0: Int): Int =
    var index = index0 + 1
    var total = 0
    while index > 0 do
      total += tree(index)
      index -= index & -index
    total
class FenwickTree {
    std::vector<int> tree;

public:
    explicit FenwickTree(int n) : tree(n + 1) {}

    void add(int index, int delta) {
        for (index++; index < tree.size(); index += index & -index) tree[index] += delta;
    }

    int sum(int index) const {
        int total = 0;
        for (index++; index > 0; index -= index & -index) total += tree[index];
        return total;
    }
};