seg tree

mail@pastecode.io avatar
unknown
c_cpp
24 days ago
2.0 kB
6
Indexable
Never
#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] = {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] = {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] = {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] = {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 > i) 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;

	query(x,i, j, b, mid, type);
	query(y,i, j, mid+1, e, type);

	info le = tree[x];
	info re = tree[y];

	if (type == 1) {
		return le.sum + re.sum;
	} else if (type == 2) {
		return max(le.max, re.max);
	} else {
		return min(le.min, re.min);
	}

}

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);
}
Leave a Comment