Structure : Fenwick Tree
Fenwick tree (BIT - Binary Indexed Tree) is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. O(n log n) preprocessing O(log n) update / query (get prefix sum)
Fenwick tree stores items-count per index, and optimized for "how many items are there between index m and n" queries.
Fenwick tree is most easily understood by considering a one-based array. Each element whose index i is a power of 2 contains the sum of the first i elements. Elements whose indices are the sum of two (distinct) powers of 2 contain the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, and that parent is found by clearing the least-significant bit in the index. "least-significant bit in the ix" = ix & -ix "contains value of ix [0...]" = ix | (ix + 1) "contains value of ix [1...]" = ix + (ix & -ix) "parent of ix [0...]" = (ix & (ix + 1)) - 1 "parent of ix [1...]" = ix - (ix & -ix)
|
// -----------------------------------------------------------------------------
// Fenwick C++
// -----------------------------------------------------------------------------
// [ix] += value
void addFenwick(std::vector<int> &t, int ix, int value)
{
while (ix < t.size()) {
t[ix] += value;
ix |= ix + 1;
}
}
// sum[0..ix]
int sumFenwick(std::vector<int> &t, int ix)
{
int sum = 0;
while (ix >= 0) {
sum += t[ix];
ix = (ix & (ix + 1)) - 1;
}
return sum;
}
// sum[a..b]
int sumFenwick(std::vector<int> &t, int a, int b)
{
return sumFenwick(t, b) - sumFenwick(t, a - 1);
}
// [ix]
int getFenwick(std::vector<int> &t, int ix)
{
int value = t[ix];
if (ix > 0) {
int lca = (ix & (ix + 1)) - 1;
ix--;
while (ix != lca) {
value -= t[ix];
ix = (ix & (ix + 1)) - 1;
}
}
return value;
}
// [ix] = value
void setFenwick(std::vector<int> &t, int ix, int value)
{
addFenwick(t, ix, -getFenwick(t, ix) + value);
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Fenwick C#
// -----------------------------------------------------------------------------
class Fenwick
{
int[] ft = null;
public Fenwick(int size)
{
ft = new int[size];
}
public Fenwick(int[] a)
{
ft = new int[a.Length];
for (int i = 0; i < a.Length; i++)
Add(i, a[i]);
}
// [ix] += value
public void Add(int ix, int value)
{
while (ix < ft.Length)
{
ft[ix] += value;
ix |= ix + 1;
}
}
// sum[0..ix]
public int Sum(int ix)
{
int sum = 0;
while (ix >= 0)
{
sum += ft[ix];
ix = (ix & (ix + 1)) - 1;
}
return sum;
}
// sum[a..b]
public int Sum(int a, int b)
{
return Sum(b) - Sum(a - 1);
}
// [ix]
public int Get(int ix)
{
int value = ft[ix];
if (ix > 0)
{
int lca = (ix & (ix + 1)) - 1;
ix--;
while (ix != lca)
{
value -= ft[ix];
ix = (ix & (ix + 1)) - 1;
}
}
return value;
}
// [ix] = value
public void Set(int ix, int value)
{
Add(ix, -Get(ix) + value);
}
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Fenwick Python
# ------------------------------------------------------------------------------
class Fenwick:
def __init__(self, size):
self._ft = [0 for i in range(size)]
def fill(self, a):
self._ft = [0 for i in range(len(a))]
for i in range(len(a)):
self.add(i, a[i])
# [ix] += value
def add(self, ix, value):
while ix < len(self._ft):
self._ft[ix] += value
ix |= ix + 1
# sum[0..ix]
def sum(self, ix):
sum = 0
while ix >= 0:
sum += self._ft[ix]
ix = (ix & (ix + 1)) - 1
return sum
# sum[a..b]
def sum2(self, a, b):
return self.sum(b) - self.sum(a - 1)
# [ix]
def get(self, ix):
value = self._ft[ix]
if ix > 0:
lca = (ix & (ix + 1)) - 1
ix -= 1
while ix != lca:
value -= self._ft[ix]
ix = (ix & (ix + 1)) - 1
return value
# [ix] = value
def set(self, ix, value):
self.add(ix, -self.get(ix) + value)
# ------------------------------------------------------------------------------
Fenwick 2D
// -----------------------------------------------------------------------------
// Fenwick C++
// -----------------------------------------------------------------------------
// (r, c) += value
void addFenwick(std::vector<std::vector<int>> &t, int r, int c, int value)
{
for (int i = r; i < t.size(); i |= i + 1)
for (int j = c; j < t[0].size(); j |= j + 1)
t[i][j] += value;
}
// sum[(0, 0), (r, c)]
int sumFenwick(std::vector<std::vector<int>> &t, int r, int c)
{
int sum = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
for (int j = c; j >= 0; j = (j & (j + 1)) - 1)
sum += t[i][j];
return sum;
}
// sum[(r1, c1), (r2, c2)]
int sumFenwick(std::vector<std::vector<int>> &t, int r1, int c1, int r2, int c2)
{
return sumFenwick(t, r2, c2) - sumFenwick(t, r1 - 1, c2) -
sumFenwick(t, r2, c1 - 1) +
sumFenwick(t, r1 - 1, c1 - 1);
}
// (r, c)
int getFenwick(std::vector<std::vector<int>> &t, int r, int c)
{
return sumFenwick(t, r, c, r, c);
}
// (r, c) = value
void setFenwick(std::vector<std::vector<int>> &t, int r, int c, int value)
{
addFenwick(t, r, c, -getFenwick(t, r, c) + value);
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Fenwick 2D C#
// -----------------------------------------------------------------------------
class Fenwick2D
{
int[][] ft = null;
public Fenwick2D(int rows, int cols)
{
ft = new int[rows][];
for (int i = 0; i < rows; i++)
ft[i] = new int[cols];
}
public Fenwick2D(int[][] a) : this(a.Length, a[0].Length)
{
for (int i = 0; i < a.Length; i++)
for (int j = 0; j < a[0].Length; j++)
Add(i, j, a[i][j]);
}
// (r, c) += value
public void Add(int r, int c, int value)
{
for (int i = r; i < ft.Length; i |= i + 1)
for (int j = c; j < ft[0].Length; j |= j + 1)
ft[i][j] += value;
}
// sum[(0, 0), (r, c)]
public int Sum(int r, int c)
{
int sum = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
for (int j = c; j >= 0; j = (j & (j + 1)) - 1)
sum += ft[i][j];
return sum;
}
// sum[(r1, c1), (r2, c2)]
public int Sum(int r1, int c1, int r2, int c2)
{
return Sum(r2, c2) -
Sum(r1 - 1, c2) -
Sum(r2, c1 - 1) +
Sum(r1 - 1, c1 - 1);
}
// (r, c)
public int Get(int r, int c)
{
return Sum(r, c, r, c);
}
// (r, c) = value
public void Set(int r, int c, int value)
{
Add(r, c, -Get(r, c) + value);
}
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Fenwick 2D Python
# ------------------------------------------------------------------------------
class Fenwick2D:
def __init__(self, rows, cols):
self._ft = [[0 for j in range(cols)] for i in range(rows)]
def fill(self, a):
self._ft = [[0 for j in range(len(a[0]))] for i in range(len(a))]
for i in range(len(a)):
for j in range(len(a[0])):
self.add(i, j, a[i][j])
# (r, c) += value
def add(self, r, c, value):
i = r
while i < len(self._ft):
j = c
while j < len(self._ft[0]):
self._ft[i][j] += value
j |= j + 1
i |= i + 1
# sum[(0, 0), (r, c)]
def sum(self, r, c):
sum = 0;
i = r
while i >= 0:
j = c
while j >= 0:
sum += self._ft[i][j]
j = (j & (j + 1)) - 1
i = (i & (i + 1)) - 1
return sum
# sum[(r1, c1), (r2, c2)]
def sum2(self, r1, c1, r2, c2):
return (self.sum(r2, c2) -
self.sum(r1 - 1, c2) -
self.sum(r2, c1 - 1) +
self.sum(r1 - 1, c1 - 1))
# (r, c)
def get(self, r, c):
return self.sum2(r, c, r, c)
# (r, c) = value
def set(self, r, c, value):
self.add(r, c, -self.get(r, c) + value)
# ------------------------------------------------------------------------------