seg tress
unknown
c_cpp
a year ago
2.0 kB
7
Indexable
#include<stdio.h> #include<string.h> #define min(a, b) ((a) < (b)) ? (a) : (b) #define max(a, b) ((a) > (b)) ? (a) : (b) int st[200009]; struct info { int sum, max, min; } tree[200009 * 4]; int n; info seg_init(int u, int b, int e) { if (b == e) { tree[u] =(struct info){st[b], st[b], st[b]}; return tree[u]; } int x = u * 2; int y = x + 1; int mid = (b+e)/2; info le = seg_init(x, b, mid); info re = seg_init(y, mid+1, e); tree[u] = (struct info){le.sum + re.sum, max(le.max, re.max), min(le.min, re.min)}; return tree[u]; } void update(int u, int i, int b, int e) { if (b > i || e < i) return; if (b == i && e == i) { tree[u] = (struct info){st[i], st[i], st[i]}; return; } int x = u * 2; int y = x + 1; int mid = (b+e)/2; update(x, i, b, mid); update(y, i, mid+1, e); info le = tree[x]; info re = tree[y]; tree[u] = (struct info){le.sum + re.sum, max(le.max, re.max), min(le.min, re.min)}; return; } int query(int u, int i, int j, int b, int e, int type) { if (e < i || b > j) return 0; if (i <= b && j >= e) { if (type == 1) { return tree[u].sum; } else if (type == 2) { return tree[u].max; } else { return tree[u].min; } } int x = u * 2; int y = x + 1; int mid = (b+e)/2; int le = query(x,i, j, b, mid, type); int re = query(y,i, j, mid+1, e, type); if (type == 1) { return le + re; } else if (type == 2) { return max(le, re); } else { return min(le, re); } } void inti (int N, int array[]) { memset(st, 0, sizeof(st)); memset(tree, 0, sizeof(tree)); for (int i = 0; i < N; i++) { st[i+1] = array[i]; } n = N; seg_init(0, 1, n); } int subscribe(int mID, int count) { st[mID] += count; update(1, mID, 1, n); return st[mID]; } int unsubscribe(int mID, int count) { st[mID] -= count; update(1, mID, 1, n); return st[mID]; } int count(int sID, int eID) { return query(0, sID, eID, 1, n, 1); } int calculate(int sID, int eID) { return query(0, sID, eID, 1, n, 2) - query(0, sID, eID, 1, n, 3); } int main() { return 0; }
Editor is loading...
Leave a Comment