느리게 갱신되는 세그먼트 트리
세그먼트 트리는 배열의 연속된 구간의 합, 최댓값, 최솟값 등을 구하는데 $O(\log N)$으로 처리할 수 있다. 특히 배열의 한 원소의 값이 변경됐을 때 $O(\log N)$으로 업데이트가 가능하다. 백준 기준 골드 상위권 티어부터 자주 사용되는 단골 알고리즘이다. 하지만 배열의 i번째 수부터 j번째 수에 v를 더하는 쿼리는 어떨까? (j-i+1...
세그먼트 트리는 배열의 연속된 구간의 합, 최댓값, 최솟값 등을 구하는데 $O(\log N)$으로 처리할 수 있다. 특히 배열의 한 원소의 값이 변경됐을 때 $O(\log N)$으로 업데이트가 가능하다. 백준 기준 골드 상위권 티어부터 자주 사용되는 단골 알고리즘이다. 하지만 배열의 i번째 수부터 j번째 수에 v를 더하는 쿼리는 어떨까? (j-i+1...
0. 발단 21-12-01 국제 전화가 왔다. 해외에서 올 전화가 없는데.. 보이스피싱인가? 근데 중국이 아닌 미국 워싱턴이네? 대수롭지 않게 넘겼다. 21-12-03 신한카드에서 체크카드 결제 거절 메시지가 왔다. 아잇.. 신종 스미싱 수법인가? 잠깐, 금액이 얼마지?? 일..십백…천만원?? 이천만원? 하하 누가 이런 사기에 속겠어...