힙 / 세그먼트 트리

힙 직접 구현하기

int heap[MAX_SIZE];
int heapSize = 0;
  
#define parent (i >> 1)
#define left (i << 1)
#define right (i << 1 | 1)
  
void heapPush(int value) {
    heap[++heapSize] = value;
    // 최소 힙
    for (register int i = heapSize; parent != 0 && heap[parent] > heap[i]; i >>= 1) {
        swap(heap[parent], heap[i]);
    }
}
  
int heapPop() {
    int ret = heap[1];
    heap[1] = heap[heapSize--];
    for (register int i = 1; left <= heapSize;) {
        if (left == heapSize || heap[left] < heap[right]) {
            if (heap[i] > heap[left]) {
                swap(heap[i], heap[left]);
                i = left;
            }
            else {
                break;
            }
        }
        else {
            if (heap[i] > heap[right]) {
                swap(heap[i], heap[right]);
                i = right;
            }
            else {
                break;
            }
        }
    }
    return ret;
}
#undef parent
#undef left
#undef right

 

세그먼트 트리

#include <iostream>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
struct Node{
    int cnt; // 총합
    int max; // 최댓값
    int min; // 최솟값
};
 
int n;
Node segtree[400000]; // 2 x N
 
void init(int N, int mSubscriber[]) {
    n = N;
 
    // 리프 노드 구성
    for(int i = 0; i < n; ++i){
        int val = mSubscriber[i];
 
        segtree[n + i].cnt = val;
        segtree[n + i].max = val;
        segtree[n + i].min = val;
    }
 
    // 부모 노드 구성
    for(int i = n - 1; i > 0; --i){
        int left = i << 1;
        int right = (i << 1) | 1;
 
        segtree[i].cnt = segtree[left].cnt + segtree[right].cnt;
        segtree[i].max = max(segtree[left].max, segtree[right].max);
        segtree[i].min = min(segtree[left].min, segtree[right].min);
    }
}
 
int subscribe(int mId, int mNum) {
    int i = mId + n - 1;
 
    segtree[i].cnt += mNum;
    segtree[i].max += mNum;
    segtree[i].min += mNum;
 
    int p = i;
    while((p >>= 1)){
        int left = p << 1;
        int right = (p << 1) | 1;
 
        segtree[p].cnt += mNum;
        segtree[p].max = max(segtree[left].max, segtree[right].max);
        segtree[p].min = min(segtree[left].min, segtree[right].min);
    }
 
    return segtree[i].cnt;
}
 
int unsubscribe(int mId, int mNum) {
    int i = mId + n - 1;
 
    segtree[i].cnt -= mNum;
    segtree[i].max -= mNum;
    segtree[i].min -= mNum;
 
    int p = i;
    while((p >>= 1)){
        int left = p << 1;
        int right = (p << 1) | 1;
 
        segtree[p].cnt -= mNum;
        segtree[p].max = max(segtree[left].max, segtree[right].max);
        segtree[p].min = min(segtree[left].min, segtree[right].min);
    }
 
    return segtree[i].cnt;
}
 
int count(int sId, int eId) {
    int ret = 0;
 
    int l, r;
    for(l = sId + n - 1, r = eId + n; l != r; l >>= 1, r >>= 1){
        if(l & 1) ret += segtree[l++].cnt;
        if(r & 1) ret += segtree[--r].cnt;
    }
 
    return ret;
}
 
int calculate(int sId, int eId) {
    int max_val = 0;
    int min_val = INT_MAX;
 
    int l, r;
    for(l = sId + n - 1, r = eId + n; l != r; l >>= 1, r >>= 1){
        if(l & 1) {
            max_val = max(max_val, segtree[l].max);
            min_val = min(min_val, segtree[l++].min);
        } 
        if(r & 1){
            max_val = max(max_val, segtree[--r].max);
            min_val = min(min_val, segtree[r].min);
        }
    }   
 
    return max_val - min_val;
}

 

다른 버전

#define maxval 1501000000
#define MAXN 200000
#include <algorithm>

using namespace std;


struct node {
	int mxval;
	int mnval;
	int sum;
	int st;
	int ed;
};


struct segTree {
	node tree[1 << 19]; //높이 ceil(log2(N))+1
	int root;
	segTree() {}
	void setup(int N, int arr[MAXN]) {
		root = 1;
		while (root < N)
        	root <<= 1;  // 리프노드가 N개 이상 있어야하므로, 리프노드 위에 총 개수는 2^18-1개
		
        for (register int i = N + 1; i <= root; i++)
        	tree[i + root - 1] = { 0, maxval, 0, N, N};
		
        root--; //리프노드에서 N개 이후로는 0 값 채우기. 그리고 구간은 다 N으로 채우기.
		
        // 리프노드에 값 채우기. N개 root+i가 idx고, i번째 값이라는 뜻
        for (register int i = 1; i <= N; i++)
        	tree[root + i] = { arr[i-1], arr[i-1], arr[i-1], i, i };
            
        // 리프 위를 하나씩 채우기. 리프 위의 idx는 root부터 1까지.
		// i는 2*i, 2*i+1 을 자식으로 가짐. 비트연산으로는 i<<1, (i<<1)|1 
		// 구간은 i<<1 의 시작, (i<<1)|1의 끝.
			
		for (register int i = root; i >= 1; i--) 
			tree[i] = {max(tree[i<< 1].mxval, tree[(i << 1) | 1].mxval),
				min(tree[i<<1].mnval, tree[(i<<1)|1].mnval), 
				tree[i<<1].sum + tree[(i<<1)|1].sum,
				tree[i << 1].st,
                tree[(i << 1) | 1].ed };
	}

	int find_max(int s, int e) {
		int ret = 0;
		for (s += root, e += root; s <= e; s >>= 1, e >>= 1) {
			if (s & 1) ret = max(ret, tree[s++].mxval);
			if (~e & 1) ret = max(ret, tree[e--].mxval);
		}
		//시작은 root+s, 끝 root+e에서 부모를 타고 가면서, 만약 범위 안에 들어오면 갱신.
		//시작은 항상 오른쪽을 타야하는데 오른쪽이 홀수니까 &1을 했을 때만 참.
		//끝은 왼쪽을 타야하니까 항상 짝수이므로 ~ 연산으로 비트를 전환하고 &1을 했을 때만 참.
		return ret;
	}

	int find_min(int s, int e) {
		int ret = maxval;
		for (s += root, e += root; s <= e; s >>= 1, e >>= 1) {
			if (s & 1) ret = min(ret, tree[s++].mnval);
			if (~e & 1) ret = min(ret, tree[e--].mnval);
		}
		return ret;
	}

	int total_cnt(int s, int e) {
		int ret = 0;
		for (s += root, e += root; s <= e; s >>= 1, e >>= 1) {
			if (s & 1) ret += tree[s++].sum;
			if (~e & 1) ret += tree[e--].sum;
		}
		return ret;
	}

	void update(int id, int num) {
		// left의 idx = root+id로 해당 값을 바꾸기.
		int i = root + id;
		tree[i].mxval += num;
		tree[i].mnval += num;
		tree[i].sum += num;
		for (i>>=1; i; i>>=1){
			//리프노드의 부모를 타고가기. 비트를 >>1 하면 됨. 
			//부모의 값은 왼쪽 오른쪽 자식을 비교해서 갱신. i<<1, (i<<1)|1 의 값을 비교.
			tree[i].mnval = min(tree[i << 1].mnval, tree[(i<<1)|1].mnval);
			tree[i].mxval = max(tree[i << 1].mxval, tree[(i << 1) | 1].mxval);
			tree[i].sum = tree[i << 1].sum + tree[(i << 1) | 1].sum;
		}
	}
	int value(int id) {
		return tree[root + id].sum;
	}
};

segTree T;
void init(int N, int mSubscriber[]) {
	T.setup(N, mSubscriber);
	return;
}

int subscribe(int mId, int mNum) {
	T.update(mId, mNum);
	return T.value(mId);
}

int unsubscribe(int mId, int mNum) {
	T.update(mId, -mNum);
	return T.value(mId);
}

int count(int sId, int eId) {
	return T.total_cnt(sId, eId);;
}

int calculate(int sId, int eId) {
	int mx = T.find_max(sId, eId);
	int mn = T.find_min(sId, eId);
	return mx-mn;
}