Create a gist now

Instantly share code, notes, and snippets.

@tanzaku /BIT.java Secret
Created Jul 25, 2017

What would you like to do?
Fenwick tree
class BIT {
final int n;
final int[] bit;
public BIT(int size) {
n = size;
bit = new int[n + 1];
}
public void clear() { Arrays.fill(bit, 0); }
// Σv[i]>=x となる最小の i を求める。
public int lowerBoundIndex(int x) {
int i = Integer.highestOneBit(n);
int cur = 0;
for(; i > 0; i >>= 1) {
if(cur < bit.length && bit[cur + i] < x) {
x -= bit[cur + i];
cur += i;
}
}
return cur;
}
// [i, j)
public int sum(int i, int j) {
return sum(j) - sum(i);
}
public int sum(int i) {
int res = 0;
for (; i > 0; i -= i & -i) {
res += bit[i];
// while(res >= mod) res -= mod;
}
return res;
}
// 1<=i<=n
public void add(int i, int x) {
if(i == 0) throw new RuntimeException();
for (; i <= n; i += i & -i) {
bit[i] += x;
// while(bit[i] >= mod) bit[i] -= mod;
}
}
}
// Binary Indexed Tree (2D)
class BIT2 {
private final int w, h;
private int[][] bit;
public BIT2(int x, int y) {
this.w = x;
this.h = y;
bit = new int[x + 1][y + 1];
}
public long sum(int x, int y_) {
long res = 0;
for (; x > 0; x -= x & -x)
for (int y = y_; y > 0; y -= y & -y)
res += bit[x][y];
return res;
}
// 1<=i<=n
public void add(int x, int y_, long v) {
for (; x <= this.w; x += x & -x)
for (int y = y_; y <= this.h; y += y & -y)
bit[x][y] += v;
}
}
class BIT3 {
private final int w, h, z;
private long[][][] bit;
public BIT3(int x, int y, int z) {
this.w = x;
this.h = y;
this.z = z;
bit = new long[x + 1][y + 1][z + 1];
}
public long sum(int x, int y_, int z_) {
long res = 0;
for (; x > 0; x -= x & -x)
for (int y = y_; y > 0; y -= y & -y)
for (int z = z_; z > 0; z -= z & -z)
res += bit[x][y][z];
return res;
}
// [x1, y1, z1] ~ [x2, y2, z2] (1 <= x1, x2, y1, y2, z1, z2 <= n)
public long sum(int x1, int y1, int z1, int x2, int y2, int z2) {
x1--; y1--; z1--;
return sum(x2, y2, z2) -
sum(x1, y2, z2) -
sum(x2, y1, z2) -
sum(x2, y2, z1) +
sum(x1, y1, z2) +
sum(x1, y2, z1) +
sum(x2, y1, z1) -
sum(x1, y1, z1);
}
// 1<=i<=n
public void add(int x, int y_, int z_, long v) {
for (; x <= this.w; x += x & -x)
for (int y = y_; y <= this.h; y += y & -y)
for (int z = z_; z <= this.z; z += z & -z)
bit[x][y][z] += v;
}
}
class BIT_ClearFast {
final int n;
final long[] bit;
final int[] id;
int gid;
public BIT_ClearFast(int size) {
n = size;
bit = new long[n + 1];
id = new int[n + 1];
}
public void clear() { gid++; }
// [i, j)
public long sum(int i, int j) {
return sum(j) - sum(i);
}
public long sum(int i) {
int res = 0;
for (; i > 0; i -= i & -i) {
if(id[i] == gid) {
res += bit[i];
}
// while(res >= mod) res -= mod;
}
return res;
}
// 1<=i<=n
public void add(int i, long x) {
if(i == 0) throw new RuntimeException();
for (; i <= n; i += i & -i) {
if(id[i] != gid) { id[i] = gid; bit[i] = 0; }
bit[i] += x;
// while(bit[i] >= mod) bit[i] -= mod;
}
}
}
class BITMin {
final int n;
final int[] bit;
public BITMin(int size) {
n = size;
bit = new int[n + 1];
clear();
}
public void clear() { Arrays.fill(bit, Integer.MAX_VALUE); }
public int sum(int i) {
int res = Integer.MAX_VALUE;
for (; i > 0; i -= i & -i) {
res = Math.min(res, bit[i]);
}
return res;
}
// 1<=i<=n
public void add(int i, int x) {
for (; i <= n; i += i & -i) {
bit[i] = Math.min(bit[i], x);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment