kkw564   4년 전

시간초과가 뜨네요


O(mnlgn)으로 해결 된다고 생각했는데 불가능한가요?


100000*1000*10 = 10억이라 안되는건가요.. 

kkw564   4년 전

펜윅 트리로 해결 할 수 있다면 그 방식이 궁금하네요

지금 제가 생각한 코드는

세그 트리가 각 배열마다 하나씩 존재한다고 생각하고 풀었는데


prefix가 아닌 세그 / 펜윅 트리로 해결하는 법은 없을까요?

dlwodnsdl   4년 전

sum(x1,x2,y1,y2)=sum(0,x2,0,y2)-sum(x1,x2,0,y2)-sum(0,x2,y1,y2)+sum(0,x1,0,y2) 이용하시면 쉽게되는것 같은데 세그먼트트리나 팬윅트리는 잘모르겠네요

kkw564   4년 전

아무래도 힘들겠죠? 세그트리에 2차원 배열을 접목하는것은요?

dotorya   4년 전

2차원 버전의 세그먼트 트리는 적용 불가능한 것으로 알고 있습니다만,
다음 쿼리 문제를 해결할 수 있는 2차원 펜윅 트리(= 바이너리 인덱스 트리)는 구현 가능합니다.
1. A[i][j] = k로 바꾸기
2. A[1...i][1...j] 구간의 합 구하기

구현은 1차원 펜윅 트리와 거의 같습니다.

dotorya   4년 전

다만 이 문제는 어차피 sum(x1,x2,y1,y2)=sum(0,x2,0,y2)-sum(x1,x2,0,y2)-sum(0,x2,y1,y2)+sum(0,x1,0,y2) 식을 써야 하고,

1번 쿼리가 없기 때문에 윗분의 말씀대로 굳이 펜윅 트리를 구현할 필요는 없을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.