11660번 - 구간 합 구하기 5
시간초과가 뜨네요
O(mnlgn)으로 해결 된다고 생각했는데 불가능한가요?
100000*1000*10 = 10억이라 안되는건가요..
펜윅 트리로 해결 할 수 있다면 그 방식이 궁금하네요
지금 제가 생각한 코드는
세그 트리가 각 배열마다 하나씩 존재한다고 생각하고 풀었는데
prefix가 아닌 세그 / 펜윅 트리로 해결하는 법은 없을까요?
아무래도 힘들겠죠? 세그트리에 2차원 배열을 접목하는것은요?
다만 이 문제는 어차피 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번 쿼리가 없기 때문에 윗분의 말씀대로 굳이 펜윅 트리를 구현할 필요는 없을 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
kkw564 7년 전
시간초과가 뜨네요
O(mnlgn)으로 해결 된다고 생각했는데 불가능한가요?
100000*1000*10 = 10억이라 안되는건가요..