세그먼트 트리3 [문제풀이] 1395번: 스위치 [문제풀이] 1395번: 스위치https://www.acmicpc.net/problem/1395 문제유형세그먼트 트리 (Lazy Propagation) Solution1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include int N, M;#define MAXT (100002*2*2)int tree[MAXT];int lazy[MAXT]; void propagate(int node, int rs, int re){ int m = (rs + re) / 2; if (lazy[.. 2018. 7. 4. [문제풀이] 14706번: 구간 합 최대 [문제풀이] 14706번: 구간 합 최대https://www.acmicpc.net/problem/14706 문제유형세그먼트 트리 Solution1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #define MAXN 50000#define MAXT (50000*2*2)int N, Q; //원소의 갯수, 구간의 갯수int tree[MAXT];#define MAX(a,b) ((a > b) ? (a) : (b)) void update_new_data(int node, int s, int e, int idx, int d){ int m; if .. 2018. 7. 4. 세그먼트 트리 (Segment Tree) 세그먼트 트리 (Segment Tree)세그먼트 트리란?구간에 대한 정보를 저장함.특정 구간의 최적화된 답을 구하는 문제에 사용.부분 구간의 최적 답들 중에서 최적 답을 구할 수 있음. 자료 저장: O(n log n)특정 구간 최적해 검색: O(log n + k) SUM TREE를 배열 기반으로 짜면, 노드마다 자식 노드의 TOTAL SUM 정보를 저장하게 됨. 구현TREE 초기 자료 구성:원본 데이터를 인자로 받아서 LEAF NODE를 찾아 하나씩 저장하는 프로세스. 배열의 크기 잡는 법:예를 들어 데이터가 1000개라면, 1000 < 2^10 이므로, TREE LEVEL은 N = 11개가 만들어져야 함. TREE[1 2018. 7. 3. 이전 1 다음