Last active
April 25, 2019 23:09
-
-
Save Chillee/b3408524ee074018ad81fedde06de15e to your computer and use it in GitHub Desktop.
Segment tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int N, M; | |
int bit[MAXN][MAXN]; | |
int sum(int x, int y) { | |
int ret = 0; | |
for (int i = x; i >= 0; i = (i & (i + 1)) - 1) | |
for (int j = y; j >= 0; j = (j & (j + 1)) - 1) | |
ret += bit[i][j]; | |
return ret; | |
} | |
void add(int x, int y, int delta) { | |
for (int i = x; i < N; i = i | (i + 1)) | |
for (int j = y; j < M; j = j | (j + 1)) | |
bit[i][j] += delta; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct seg { | |
int seg[2 * MAXN][2 * MAXN]; | |
void modify(int qr, int qc, int val) { | |
qr += N, qc += M; | |
seg[qr][qc] = val; | |
for (int r = qr; r > 0; r >>= 1) { | |
for (int c = qc; c > 0; c >>= 1) | |
seg[r][c >> 1] = seg[r][c] + seg[r][c ^ 1]; | |
seg[r >> 1][qc] = seg[r][qc] + seg[r ^ 1][qc]; | |
} | |
} | |
int query2(int l, int r, int row) { | |
int res = 0; | |
for (l += M, r += M; l < r; l >>= 1, r >>= 1) { | |
if (l & 1) | |
res += seg[row][l++]; | |
if (r & 1) | |
res += seg[row][--r]; | |
} | |
return res; | |
} | |
int query(int u, int d, int l, int r) { | |
int res = 0; | |
for (u += N, d += N; u < d; u >>= 1, d >>= 1) { | |
if (u & 1) | |
res += query2(l, r, u++); | |
if (d & 1) | |
res += query2(l, r, --d); | |
} | |
return res; | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template <typename T> struct Seg { | |
const int N; | |
vector<T> seg; | |
T unit; | |
const function<T(T, T)> combine; | |
Seg(int n, T arr[], T u, function<T(T, T)> cF) : N(n), unit(u), combine(cF), seg(N * 2) { | |
for (int i = 0; i < N; i++) | |
seg[i + N] = arr[i]; | |
build(); | |
} | |
void build() { | |
for (int i = N - 1; i > 0; --i) | |
seg[i] = combine(seg[i << 1], seg[i << 1 | 1]); | |
} | |
void modify(int p, T value) { | |
for (seg[p += N] = value; p > 0; p >>= 1) | |
seg[p>>1] = combine(seg[p], seg[p ^ 1]); | |
} | |
T query(int l, int r) { | |
T resl = unit; | |
T resr = unit; | |
for (l += N, r += N; l < r; l >>= 1, r >>= 1) { | |
if (l & 1) | |
resl = combine(resl, seg[l++]); | |
if (r & 1) | |
resr = combine(seg[--r], resr); | |
} | |
return combine(resl, resr); | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
gp_hash_table<int, int, chash> seg; | |
int get(int x) { return (seg.find(x) == seg.end()) ? 0 : seg[x]; } | |
void modify(int p, int val) { | |
for (seg[p += N] = val; p > 0; p >>= 1) { | |
seg[p >> 1] = get(p) + get(p ^ 1); | |
} | |
} | |
int query(int l, int r) { | |
int res = 0; | |
for (l += N, r += N; l < r; l >>= 1, r >>= 1) { | |
if (l & 1) | |
res += get(l++); | |
if (r & 1) | |
res += get(--r); | |
} | |
return res; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct Tree { | |
Tree *pl, *pr; | |
int nl = 0, nr = 0, val = 0, lazy = 0; | |
void updateVal() { val = pl->val + pr->val; } | |
void propagate() { pl->apply(lazy), pr->apply(lazy), lazy = 0; } | |
void apply(int x) { lazy += x, val += (nr - nl) * x; } | |
Tree(int l, int r, int A[]) { | |
nl = l, nr = r; | |
if (nl + 1 == nr) { | |
val = A[nl]; | |
return; | |
} | |
pl = new Tree(nl, nl + nr >> 1, A); | |
pr = new Tree(nl + nr >> 1, nr, A); | |
updateVal(); | |
} | |
void modify(int l, int r, int x) { | |
if (l <= nl && nr <= r) { | |
apply(x); | |
return; | |
} | |
if (l >= nr || nl >= r) | |
return; | |
propagate(); | |
pl->modify(l, r, x); | |
pr->modify(l, r, x); | |
updateVal(); | |
} | |
int query(int l, int r) { | |
if (l <= nl && r >= nr) | |
return val; | |
if (l >= nr || nl >= r) | |
return 0; | |
propagate(); | |
return pl->query(l, r) + pr->query(l, r); | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct Tree { | |
Tree *pl, *pr; | |
int nl = 0, nr = 0, val = 0; | |
void updateVal() { val = pl->val + pr->val; } | |
Tree(int l, int r, int A[]) { | |
nl = l, nr = r; | |
if (nl + 1 == nr) { | |
val = A[nl]; | |
return; | |
} | |
pl = new Tree(nl, nl + nr >> 1, A); | |
pr = new Tree(nl + nr >> 1, nr, A); | |
updateVal(); | |
} | |
void modify(int p, int x) { | |
if (p < nl || nr <= p) { | |
return; | |
} | |
if (nl + 1 == nr) { | |
val = x; | |
return; | |
} | |
pl->modify(p, x); | |
pr->modify(p, x); | |
updateVal(); | |
} | |
int query(int l, int r) { | |
if (l <= nl && r >= nr) | |
return val; | |
if (l >= nr || nl >= r) | |
return 0; | |
return pl->query(l, r) + pr->query(l, r); | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int seg[2 * MAXN]; | |
void modify(int l, int r, int val) { | |
for (l += N, r += N; l < r; l >>= 1, r >>= 1) { | |
if (l & 1) | |
seg[l++] += val; | |
if (r & 1) | |
seg[--r] += val; | |
} | |
} | |
int query(int p) { | |
int res = 0; | |
for (p += N; p > 0; p >>= 1) | |
res += seg[p]; | |
return res; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int seg[2 * MAXN]; | |
void build() { | |
for (int i = N - 1; i >= 0; i--) | |
seg[i] = seg[i << 1] + seg[i << 1 | 1]; | |
} | |
void modify(int p, int val) { | |
for (seg[p += N] = val; p > 0; p >>= 1) | |
seg[p >> 1] = seg[p] + seg[p ^ 1]; | |
} | |
int query(int l, int r) { | |
int res = 0; | |
for (l += N, r += N; l < r; l >>= 1, r >>= 1) { | |
if (l & 1) | |
res += seg[l++]; | |
if (r & 1) | |
res += seg[--r]; | |
} | |
return res; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Lazy Segtrees form a semi-ring, where update=multiplication, query=addition. We need that
U(Q(l), Q(r)) = Q(U(l), U(r))