일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 프로그래밍
- css
- radare2
- C언어
- 리눅스커널
- 시스템해킹
- pwn.college
- 컴퓨터구조
- 시스템
- 알고리즘
- 어셈블리어
- write up
- wargame
- pwncollege
- 커널
- Bandit
- 포너블
- 하드링크
- 리눅스 커널
- 시그널
- Pwnable.kr
- 시스템프로그래밍
- Leviathan
- 리버싱
- 시스템 프로그래밍
- kernel
- 리눅스
- 워게임
- multiplexing
- C++
Archives
- Today
- Total
Computer Security
#9 인덱스 트리 본문
인덱스 트리
트리 구조로 구간 합 구하기
-세그먼트 트리는 구현하는 과정이 복잡하고 어렵다는 점에서 구간 합을 더 쉽게 구할 방법이 필요하다.
-인덱스 트리는 구현이 매우 간단하다.
-인덱스 트리를 활용해 구간 합을 구하는 과정도 O(logN)의 시간 복잡도를 가진다.
-인덱스 트리는 세그먼트 트리에 비해서 메모리 효율성이 높다.
특정한 숫자의 마지막 비트 구하기
-특정한 숫자 A의 가장 마지막 비트를 구하고자 할 때는 A& -A를 구하면 된다.
ex) A가 14일 때 이를 비트 형태로 표현하면,
A = 00000000 00000000 00000000 00001110
-A = 11111111 11111111 11111111 11110010
A & -A = 00000000 00000000 00000000 00000010
이다.
마지막 비트를 이용해 트리 구조 만들기
-각 인덱스에 대해 마지막 비트를 '내가 저장하고 있는 값들의 개수'로 표현한다.
예를들어 14라면, 마지막비트는 2가 나오고, 이는 14가 13,14의 구간합을 가지고 있다로 해석된다.
코드예시
//1부터 N까지의 구간 합 구하기
#include <stdio.h>
#define NUMBER 7
int tree[NUMBER];
int sum(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
// 마지막 비트만큼 빼면서 앞으로 이동
i -= (i & -i);
}
return res;
}
//특정 인덱스 수정하기
void update(int i, int dif) {
while (i <= NUMBER) {
tree[i] += dif;
// 마지막 비트만큼 더하면서 뒤로 이동
i += (i & -i);
}
}
//구간 합 계산 함수 구현하기
int getSection(int start, int end) {
return sum(end) - sum(start - 1);
}
//사용하기
int main(void) {
update(1, 7);
update(2, 1);
update(3, 9);
update(4, 5);
update(5, 6);
update(6, 4);
update(7, 1);
printf("1부터 7까지의 구간 합: %d\n", getSection(1, 7));
printf("인덱스 6의 원소를 +3만큼 수정\n");
update(6, 3);
printf("4부터 7까지의 구간 합: %d\n", getSection(4, 7));
system("pause");
}
결과값
'프로그래밍 > C언어 알고리즘' 카테고리의 다른 글
#11 라빈 카프 문자열 매칭 (0) | 2022.06.11 |
---|---|
#10 KMP 문자열 매칭 (0) | 2022.06.10 |
#8 세그먼트 트리 (0) | 2022.05.10 |
#7 다익스트라의 최단 경로 (0) | 2022.05.08 |
#6. 프림 알고리즘 (0) | 2022.05.07 |
Comments