2차원 펜윅 트리2 펜윅 트리(Fenwick tree, BIT) - 기본, 2D, lazy propagation(range update - point query, range update - range query) 목차 ※ References에 적어둔 여러 글을 보며 공부한걸 나중에 까먹지 않기 위해 제가 이해한 내용을 제가 이해한 방식으로 필기 해두는식으로 적은 글 입니다. 그러니 개념을 더 제대로 살펴보시려면 References의 잘써둔 글들을 참고해주세요. 그나마 이 글의 장점이라면 제가 수학에 매우 약하기 떄문에 제가 이해한 방식으로 적어두면 다른 분들은 훨씬 금방 이해하심. 틀린거 있으면 알려주세요! ※ 용어 : 이하 글에서 구간합은 'A부터 B까지의 합', 누적합은 '1부터 N까지의 합', 누적합 알고리즘은 prefix sum 알고리즘을 뜻합니다. ※ 기본적으로 중간 중간에 있는 코드 예시는 c++, java 모두 통용되는 코드로 작성했습니다. 어차피 구현이 간단한 부분들이므로 어떤 언어를 사용하던지 이.. 2022. 8. 15. [자바, C++] 백준 11658 - 구간 합 구하기 3 (java cpp) 문제 : boj11658 필요 알고리즘 개념 다차원 펜윅 트리, 세그먼트 트리 펜윅 트리 혹은 세그먼트 트리를 2차원에 대해 적용할 수 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 다차원 펜윅 트리, 세그먼트 트리 등으로 풀 수 있는 기본형태의 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트리 글에서 '응용 1' 부분을 읽어보면 이 문제를 풀 수 있다. 코드(C++) : github #include #.. 2022. 8. 15. 이전 1 다음
