ax = 1 (mod m)에서 x가 존재하기 위한 필요충분조건 gcd(a, m) = 1
a의 범위를 [1,m-1]로 잡고, m을 소수로 만들면 항상 x가 존재한다.
연산의 결합법칙이 성립해야하고, 항등원이 존재해야한다.
변경이력을 모두 남기는 자료구조 변경이 한 번 일어날 때마다 Log(N)개의 노드만 추가함으로써 PST를 구현할 수 있다. 일반 세그먼트 트리와는 다르게 시간축과 인덱스축이 존재하게 되는데 2차원 문제를 풀 때 사용한다.
a + b ≥ 2*sqrt(ab)
N개의 요소를 가지는 배열을 B 크기만큼 자르면 N / B개의
BOJ 14438
포화이진트리 배열로 저장이 가능하다.
left: 2x, right: 2x+1