11505번: 구간 곱 구하기

11505번: 구간 곱 구하기사용 언어: C++ 풀이구간 합 구하기 문제와 유사. 구간의 곱을 구하는 것이므로 트리는 똑같이 만든다. 한 가지 다른 점은, 트리를 만들때 % MOD를 한다는 것인데, 어차피 마지막에 한번 Mod를 하나 중간 계속 Mod를 하나 결과는 같다. 그래서 Overflow가 안나게 매번 % MOD를 해준다는 것. Query에서도 곱을 하면서 % MOD를 해준다.#include using namespace std;typedef long long ll;const int MOD = 1'000'000'007;constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); } for (int i..

2042번: 구간 합 구하기

2042번: 구간 합 구하기사용 언어: C++ 풀이리프 노드들은 입력 값들, 부모 노드들은 값들의 합으로 설정해서 O(log n)으로 구간의 합을 구하는 세그먼트 트리 문제다. 주의할 점은 a == 1일때 c가 int 범위를 넘어서 오버플로우가 발생할 수 있어서 long long을 설정해야한다.#include using namespace std;typedef long long ll;// SZ는 N보다 크거나 같은 2^k 꼴의 수 (2^20 == 1,048,576 > 1,000,000)constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); // 세그먼트 트리 초기화 } for (int i = 0; i..