seg tress

 avatar
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