일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- ViewModel
- HTTP
- CollapsingToolbarLayout
- Behavior
- DataBinding
- 알림
- CustomView
- onLayout
- 코틀린
- activity
- Algorithm
- View
- AppBarLayout
- lifecycle
- 안드로이드
- 백준
- BOJ
- CoordinatorLayout
- room
- kotlin
- notification
- 알고리즘
- onMeasure
- hilt
- sqlite
- Coroutine
- Navigation
- recyclerview
- Android
- LiveData
- Today
- Total
목록Binary Indexed Tree (2)
개발일지
개념 각 노드에 구간의 정보를 저장하여 Query, Update를 빠르게 처리할 수 트리다. 작동원리 트리로 구간의 정보를 저장하여 최악의 경우 트리의 높이만큼 트리를 탐색하여 Query와 Update를 수행할 수 있다. 트리의 성질 왼쪽 자식노드 : index * 2 오른쪽 자식노드 : index * 2 + 1 Query 참조하는 범위가 구간을 완전히 벗어나면 0을 Return한다. 참조하는 범위가 구간에 완전히 겹치면 Tree에 저장된 값을 Return한다. 참조하는 범위가 구간에 걸치면 Tree에 더 깊은 Level을 참조한다. 3-6 구간의 정보를 얻으려면 5, 6을 참조한다. 1-7 구간의 정보를 얻으려면 2, 6, 14를 참조한다. 1-8 구간의 정보를 얻으려면 1을 참조한다. Update 참..
개념 각 인덱스는 최하위 비트의 값만큼 구간을 저장하고 이를 이용하여 구간의 합을 빠르게 찾을 수 있다. => 1, 3, 5, 7은 최하위 비트의 값이 1 -> 구간의 길이가 1만큼의 합을 저장 => 2, 6은 최하위 비트의 값이 2 -> 구간의 길이가 2만큼의 합을 저장 => 4는 최하위 비트의 값이 4 -> 구간의 길이가 4만큼의 합을 저장 => 8은 최하위 비트의 값이 8 -> 구간의 길이가 8만큼 합을 저장 작동원리 최하위 비트를 구하는 법 index & -index Query 1-3 구간의 합을 구하면 트리에서 2, 3을 더한다. 3(0011)에 저장된 값을 더하고 최하위 비트(0001)를 뺀다. => 2(0010) 2(0010)에 저장된 값을 더하고 최하위 비트(0010)를 뺀다. => 0(0..