고급자료구조

Transcription

1 배상원

2 Binary Search Tree (BST) Balanced BSTs Red-Black Tree Splay Tree Geometric Search Trees Range Tree Interval Tree Segment Tree Binary Indexed Tree

3

4 Definition (recursive) An empty tree is a binary tree A tree with a root node whose left and right subtrees are binary trees is a binary tree level = 0 I level = 1 level = 2 A B F height = 3 J K L level = 3 E 4

5 Binary tree with BST property y in left subtree of x, then key[y] key[x]. y in right subtree of x, then key[y] key[x]. x A B E F I J K L y y 5

6 Linked data structure root(t) : pointer to root node of a BST T Each node contains fields: key left : pointer to left child (root of left subtree) right : pointer to right child (root of right subtree) p : pointer to parent. p[root[t]] = NIL (optional). key 6

7 Supports dynamic set operations Search Minimum Maximum Successor Predecessor Insert Delete 연산수행시간 : O(h) h : height of binary search tree h could be n in worst case 7

8 Inorder-Tree-Walk (x) 1. if x NIL 2. then Inorder-Tree-Walk(left[p]) 3. print key[x] 4. Inorder-Tree-Walk(right[p]) Running Time: O(n) A B E F I J K L A B E F I J K L 8

9 Tree-Search(x, k) 1. if x = NIL or k = key[x] 2. then return x 3. if k < key[x] 4. then return Tree-Search(left[x], k) 5. else return Tree-Search(right[x], k) Running Time: O(h) A B E F I J K L 9

10 Tree-Minimum(x) Tree-Maximum(x) 1. while left[x] NIL 1. while right[x] NIL 2. do x left[x] 2. do x right[x] 3. return x 3. return x A B E F I J K L 10

11 Successor of node x: node y such that key[y] is the smallest key that is greater than key[x] The successor of the largest key is NIL. Successor of B? Successor of F? A B E F I J K L 11

12 Two cases for searching If node x has a non-empty right subtree x s successor is the minimum in the right subtree of x. If node x has an empty right subtree y is the successor of x x is the predecessor of y x y y x Go up through right child pointers, and finally through one left child pointer 12

13 Tree-Successor(x) 1. if right[x] NIL 2. then return Tree-Minimum(right[x]) 3. y p[x] 4. while y NIL and x = right[y] 5. do x y 6. y p[y] 7. return y Running Time: O(h) 13

14 Symmetric to Successor 14

15 Tree-Insert(T, z) 1. y NIL 2. x root[t] A 3. while x NIL 4. do y x 5. if key[z] < key[x] 6. then x left[x] 7. right[x] else x 8. p[z] y 9. if y = NIL 10. then root[t] z 11. else if key[z] < key[y] 12. then left[y] z 13. else right[y] z B E I G J K F Running Time: O(h) L 15

16 3 Cases : Delete(T, x) case 1: x has no children Remove leaf node x case 2: x has one children Make p[x] point to child case 3: x has two children Swap x with its successor and perform case 1 or case 2 to delete it I delete F delete G delete B, I A B E G F J K L Running Time: O(h) 16

17 Red-Black Tree Splay Tree

18 Supports dynamic set operations Search, Minimum, Maximum, Successor, Predecessor Insert, Delete Binary Search Tree 연산수행시간 : O(h) h : height of binary search tree h can be n in worst case Balanced Binary Search Tree h = O(log n) always! 연산수행시간 : O(h) = O(log n) AVL Tree 2-3 Tree Red-Black Tree Splay Tree 18

19 Red-black tree (RBT) Binary search trees augmented with node color Operations designed to guarantee that the height h = O(log n) 19

20 A Red-Black Tree is a BST satisfying 5 Properties 1. Every node is either red or black 2. Every leaf (NULL pointer) is black Note: this means every real node has 2 children 3. If a node is red, then both children are black Note: there are no 2 consecutive reds on a path 4. Every path from a node to descendent leaf contains the same number of black nodes 5. The root is always black 20

21 Example Property 1 Property 2 Property 3 Property 4 Property 5 By properties 3 and 4, the height of RBT is O(log n) 21

22 Operations Search, Minimum, Maximum, Predecessor, Successor O(log n) time Insertion, Deletion Restructure RBT to guarantee the height to be O(log n) 22

23 Color this tree: RBT Properties 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 23

24 Insert 8 Where does it go? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 24

25 Insert 8 Where does it go? 5 9 What color should it be? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 25

26 Insert 8 Where does it go? 5 9 What color should it be? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 26

27 Insert 11 Where does it go? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 27

28 Insert 11 Where does it go? What color? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 11 28

29 Insert 11 Where does it go? What color? Can t be red! (#3) Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 11 29

30 Insert 11 Where does it go? What color? Can t be red! (#3) Can t be black! (#4) 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black

31 Insert 11 Where does it go? What color? Solution: recolor the tree 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black

32 Insert 10 Where does it go? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 11 32

33 Insert 10 Where does it go? What color? Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black

34 Insert 10 Where does it go? What color? A: no color! Tree is too imbalanced Must change tree structure to allow recoloring Goal: restructure tree in O(log n) time

35 Rotation : Basic operation to restructure RBT y rightrotate(y) x A x B C leftrotate(x) A B y C Preserves the in-order property of BST 35

36 Example leftrotate(9) rightrotate(12) Preserves the inorder property of BST 36

37 Basic idea of Insertion Insert x into tree (as in BST) Color x red Only RBT Property 3 may be violated (if parent[x] is red) If so, move the violation up tree until a place is found where it can be fixed Total time will be O(log n) 37

38 rbinsert(x) treeinsert(x); x->color = RED; // Move violation of #3 up tree, maintaining #4 as invariant: while (x!=root && x->p->color == RED) if (x->p == x->p->p->left) // p(x) is left child of parent y = x->p->p->right; // y : uncle of x if (y->color == RED) x->p->color = BLACK; y->color = BLACK; x->p->p->color = RED; x = x->p->p; else // y->color == BLACK if (x == x->p->right) x = x->p; leftrotate(x); x->p->color = BLACK; x->p->p->color = RED; rightrotate(x->p->p); else // x->p == x->p->p->right (same as above, but with right & left exchanged) T.root->color = BLACK; Case 1: uncle is RED Case 2 Case 3 38

39 if (y->color == RED) x->p->color = BLACK; y->color = BLACK; x->p->p->color = RED; x = x->p->p; Case 1: Uncle y is red In figures below, all s are equal-black-height subtrees A C D y case 1 A C new x D B x B 39

40 40 C A D B C A D B x y new x case 1 B x C A D C A D y new x B x case 1

41 if (x == x->p->right) x = x->p; leftrotate(x); // continue with case 3 code Case 2: Uncle y is black Node x is a right child Transform to case 3 via a left-rotation A C y case 2 B C y B x A x 41

42 x->p->color = BLACK; x->p->p->color = RED; rightrotate(x->p->p); Case 3: Uncle y is black Node x is a left child Change colors; rotate right B C y case 3 x A B C A x 42

43 x is a left/right child of a parent Left child Right child Root cases Case 1 Case 2 Case 3 Symmetric hint Move the red color to a parent, and continue the loop Run case 2 and stop the loop Run case 3 and stop the loop Change the color to black 43

44 y 4 x case 1 44

45 y 1 7 x case 2 45

46 y x case 3 46

47 7 x

48 Basic idea to Deletion (rbdelete(t, z)) delete z from tree (as in TreeDelete(T, z) for BSTs) Let y be the node that has actually been deleted and x be a child of y (as declared in rbdelete) Only RBT Property 4 might be violated (if y is black) If so, move the violation up tree until we find a place where it can be fixed Total time will be O(log n) // deletion operation if (y->color) == BLACK) rbdeletefixup(t, x); y delete y return y; x x 48

49 rbdeletefixup(t, x) while (x!= T.root && x->color == BLACK) if (x == x->p->left) // x is a left child w = x->p->right // w is the sibling of x if (w->color == RED) w->color = BLACK; // case 1 x->p->color = RED; // case 1 Case 1 leftrotate(t,x->p); // case 1 w = x->p->right; // case 1 if (w->left->color == BLACK && w->right->color == BLACK) w->color == RED; // case 2 Case 2 x = x->p; // case 2 else if w->right->color == BLACK) w->left->color = BLACK; // case 3 w->color = RED; // case 3 Case 3 rigthrotate(s, x); // case 3 w = x->p->right; // case 3 w->color = x->p->color; // case 4 x->p->color = BLACK; // case 4 w->right->color = BLACK; // case 4 Case 4 leftrotate(t, x->p); // case 4 x->t.root; else // x == x->p->right (same as above, but with right & left exchanged) x->color = BLACK; 49

50 After a node y is deleted Node y has one child x Move the black to child node x of y move the extra black up tree until a place is found where it can be fixed y delete y stop y delete y x x x x move the extra black up tree 50

51 if (w->color == RED) w->color = BLACK; x->p->color = RED; leftrotate(t,x->p); w = x->p->right; Case 1: sibling w is red After rotation, the case 1 is converted into cases 2, 3, or 4 x A B D w case 1 B D new w E C E x A C 51

52 if (w->left->color == BLACK && w->right->color == BLACK) w->color == RED; x = x->p; Case 2,3,4: sibling w is black Case 2 : both children of w are black x A B D w case 2 new x A B D w C E C E 52

53 53 B A D x w case 2 C E B A D w C E When parent of x is red, as it comes from case 1: Color the sibling w with red Move up the one extra black to the parent Terminate the delete routine

54 When parent of x is black: Color the sibling w with red Move up the one extra black to the parent Restart the loop from the parent of x. x A B D w case 2 new x A B D w C E C E 54

55 if (w->left->color == BLACK && w->right->color == BLACK) else if (w->right->color == BLACK) w->left->color == BLACK; w->color = RED; rightrotate(t, w); w = x->p->right; Case 3,4: at least one of children of w is red. Transform case 3 into case 4. x A B C D w E case 3 A B new w C D E 55

56 w->color = x->p->color; x->p->color = BLACK; w->right->color = BLACK; leftrotate(t, x->p); x = T.root; Case 4: right child of w is red Terminate delete routine at the next loop x A B D w case 4 B D E C E A C 56

57

58 Splay Tree Balanced binary search tree Do not have any other information (like color in red-black tree) Restructure tree after each operation (search, insert, delete) so the tree is called Self-reconstructing, self-adjusting, self-organizing tree After search, insert operation Move the node to the root of the tree After delete operation Move the adjacent node to the deleted node to the root Splaying Moves a node to the root by a sequence of rotation 58

59 Self-reconstructing method (1) By left, right rotation root α x A β C γ α A β C γ 59

60 Self-reconstructing method (1) By left, right rotation root C C A x α A B β γ δ α A β B δ γ α β B γ C δ 60

61 Self-reconstructing method (1) Problem: might make the tree unbalanced C D E F C D E A F D E F A B A B B C

62 Self-reconstructing method (1) Problem: might make the tree unbalanced A E D F A D F E D A E F B C B C B C 62

63 Self-reconstructing method (2) By zig, zig-zag, zig-zig steps Zig step When parent of node x is the root One left or right rotation root α x A β C γ α A β C γ 63

64 Zig-zag step When parent of node x is not the root 64 C δ A x α B γ β B A γ δ α β C A C β α δ γ B x x

65 Zig-zig step When parent of node x is not the root y C A x x α A B β γ δ α β B γ C y δ 65

66 F F F A E E A F D D D D C A B E B E B B C C A C 66

67 Splay a node Move it to the root by a sequence of rotation After Search(T, x) If x does not exist Splay the last accessed node If x exist Splay the node x After Insert(T, x) Insert x, and splay the node After Delete(T, x) Delete x, and splay the parent node of the actual node deleted Amortized time complexity O(m log n) where m is the number of operations 67

68 Finding k-th element Computing the rank

69 BSTs support Minimum, Maximum, Search, Insertion, Deletion More Query Operations Selection and Rank Selection: k 번째로작은데이터를구하시오. Rank: 주어진데이터가전체데이터에서몇번째인지, 즉순위 (rank) 를계산하시오. With balanced binary search tree (e.g., red-black tree) Query time complexity: O(log n) Insertion and deletion are allowed 69

70 To handle dynamic order statistic queries Based on red-black tree (or any other BSTs) An additional field size : 주어진노드를루트로하는 subtree 의노드의수 x->size = x->left->size + x->right->size key size

71 Selection: find k-th smallest element OSselect(x, k) r = x->left->size + 1; if (r == k) return x; else if (r > k) return OSselect(x->left, k); else return OSselect(x->right, k-r); key size

72 Rank: compute the rank of a node x OSrank(T, x) r = x->left->size + 1; y = x; while (y!= T.root) if (y == y->p->right) r += y->p->left->size + 1; y = y->p; return r; key size

73 Insertion Size field 값수정 루트노드에서단말노드로내려가면서, 지나가는모든노드의 size 값을 1 증가. 입력데이터를저장하는노드의 size 값을 1 로지정. 각 left, right rotation 마다다음과같이 size 값수정 y rightrotate(y) x x 7 leftrotate(x) y

74 Deletion Size field 값수정 노드를 delete 한후, 이노드의부모노드부터시작하여루트노드까지올라가면서지나가는모든노드의 size 값을 1 감소. 각 left, right rotation 마다 insert 연산에서와같이 size 값수정 74

75

76 1 차원 Range Query Range Query n 개의실수 S = {a 1, a 2,, a n } 이주어졌을때, 주어진폐구간 (query interval) I=[b 1, b 2 ] 에포함되는 S 의모든원소를찾는문제 Range reporting: report all data Range counting: count the number of data Dynamic operation Insertion, deletion Range tree Supports range queries Range counting: O(log n) Range reporting: O(log n + k) 76

77 1 차원 Range Tree Balanced binary search tree Properties 단말노드는 n 개의실수 {a 1, a 2,, a n } 를원소로한다. 내부노드는 n-1 개의실수 {a 1, a 2,, a n-1 } 를원소로한다. 77

78 Example

79 Query reporting: range [l, r] Step 1: search l, r. 최종적으로도달한단말노드를 t l, t r Step 2: v split 계산 루트노드로부터시작하여단말노드로내려가면서노드 x 의 key 값이 [l, r] 에포함되는첫노드 Step 3: v split 로부터단말노드 t l 로내려가면서 어떤노드 x 의왼쪽 child 로내려갈경우에는이노드 x 의오른쪽 subtree 에속하는모든단말노드의점들은모두주어진 range 에포함되므로이노드들을모두 report 한다. 어떤노드 x 의오른쪽 child 로내려갈경우에는아무런작업을하지않는다. Step 4: v split 로부터단말노드 t r 로내려가면서 (Step 3 의내용과유사함 ) Time complexity : O(log n + k) 79

80 range [l, r] V split t l t r 80

81 query reporting: [6,32]

82 RangeReport1D(T, l, r) // range R = [l, r] vsplit = FindSplitNode(T, l, r); if (vsplit is leaf node) report if vsplit->key is in range R; else v = vsplit->left; while (v is not leaf node) if (l <= v->key) report all leaf nodes of subtree v->right v = v->left; else v = v->right; report if leaf node v->key is in range R; v = vsplit->right; // similarly, symmetrically do the same as above // right & left exchanged FindSplitNode(T, l, r) // range = [l, r] v = T.root; while (v is not a leaf && (r <= v->key or l >= v->key)) if (r <= v->key) v = v->left; else v = v->right; return v; 82

83 Time complexity : O(log n) - Use field size

84 2 차원 Range Query 2 차원평면상에 n 개의점 P = {p 1, p 2,, p n } 이주어졌을때, 주어진직사각형 R=[a 1, a 2 ][b 1, b 2 ] 영역에포함되는 P 의모든점를계산하는문제 b 2 P R b 1 a 1 a 2 84

85 2D Range Query Range Query Range reporting: report all data elements Range counting: count the number of data elements 2D Range tree supports 2D range queries Time complexity Range counting: O(log 2 n) Range reporting: O(log 2 n + k) allows dynamic operations Insertion and deletion 85

86 Construction 1. 먼저 P 에속하는모든점들의 x- 좌표를기준으로 1 차원 range tree T 를만든다. 이트리에서는앞그림에서와같이 x- 좌표가 [a 1, a 2 ] 인수직구간에포함되는모든점에대한 query 가가능 2. 그다음에위에서만든트리 T 의모든내부노드 t 마다, t 를루트로하는 T 의부분트리에속하는모든단말노드에해당하는점들의집합을 Q t 라고하자. Q t 에속하는모든점들에대하여 y- 좌표를기준으로 1 차원 range tree 를만들어이트리 ( 의 root) 를노드 t 에연결한다. 86

87 Range tree on x-coordinates T Range tree on y-coordinates Q t t Q t 87

88 88

89 Range reporting: query range [a, b]x[c, d] 1D range query 를이용 X- 축의좌표로만들어진 range tree 에대하여구간 [a, b] 에대하여 range query 수행 어떤노드 x 에대하여 1 차원 range reporting 하는대신에 노드 x 에연결된 y- 좌표로만들어진 1D range tree 에대하여구간 [c, d] 로다시한번더 1 차원 range reporting 을수행 Time complexity : O(log 2 n + k) 89

90 x-range tree y-range tree d t a b c Q t Q t 90

91 RangeReport2D(T, a, b, c, d) // range R = [a, b] [c, d] vsplit = FindSplitNode(T, a, b); if (vsplit is leaf node) report if vsplit->key is in range R; else v = vsplit->left; while (v is not leaf node) if (l <= v->key) RangeReport2D(v->right->Ty, c, d); v = v->left; else v = v->right; report if leaf node v->key is in range R; v = vsplit->right; // similarly, symmetrically do the same as above // right & left exchanged 91

92

93 Closed Intervals ( 폐구간 ) [a, b] (a b) [a, b] [c, d] iff (a d) and (c b) [a, b] [c, d] = iff (a > d) or (c > b) a b c d c d a b a c b d 93

94 Operations IntervalInsert(T, x) : Interval 트리 T 에폐구간을저장하는노드 x 를추가한다. IntervalDelete(T, x) : Interval 트리 T 에서노드 x 를제거한다. IntervalSearch(T, i) : 폐구간 i 와서로겹치는한개 ( 모든 ) 구간을찾는다. Interval Tree Balanced Binary Search Tree 각구간 [low, high] 의 low 값을 key 값으로만든다. Node x x->int : interval stored in node x x->max : 노드 x를루트로하는 subtree 의모든노드에저장된구간의최대값. 94

95 [8,9] 23 [16,21] 30 [25,30] 30 interval max [5,8] 10 [15,23] 23 [17,19] 20 [26,26] 26 [0,3] 3 [6,10] 10 [19,20] 20 x->max = MAX(x->int->high, x->left->max, x->right->max) 95

96 Search: IntervalSearch(T, i) : 폐구간 i 와서로겹치는한개구간을계산한다. IntervalSearch(T, i) x = T.root; while (x!= NULL and i does not overlap x->int) if (x->left!= NULL and x->left->max >= i->low) x = x->left; else x = x->right; return x; Others Q1: Interval tree 에서주어진구간과겹치는모든구간을찾는 IntervalSearchAll() 연산을구현하시오. Q2: Interval tree 에저장된구간과가장많이겹치는임의의점을찾는알고리즘을구현하시오. 96

97 Operations IntervalInsert(T, x) : Interval 트리 T 에폐구간을저장하는노드 x 를추가한다. IntervalDelete(T, x) : Interval 트리 T 에서노드 x 를제거한다. IntervalSearch(T, i) : 폐구간 i 와서로겹치는모든구간을찾는다. IntervalPointQuery(T, q) : 점 q 를포함하는모든구간을찾는다. IntervalSum(T) : T 에포함된모든 interval 의합집합의길이를계산한다. 97

98 Interval Tree Fully dynamic structure 어떠한 interval 도 insert, delete 될수있다. 가능한 Operation 이제한적 Segment Tree Semi-dynamic structure interval 이가질수있는끝점의집합 P 가정해짐 끝점이 P 에속하는 interval 만 insert, delete 가능 더많은 Operation 이쉽게구현가능 IntervalPointQuery, IntervalSum 등에유리 98

99 Construction n 개의폐구간 I = {[a 1, b 1 ], [a 2, b 2 ],, [a n, b n ]} 주어질때, p 1, p 2,, p m 폐구간 I 에속하는구간들의모든끝점을오름차순으로나열 1 차원직선을아래와같은구간으로나눔 기본구간 (elementary interval) 이라고부름 (-, p 1 ), [p 1, p 1 ], (p 1, p 2 ), [p 2, p 2 ], (p 2, p 2 ),, (p m-1, p m ), [p m, p m ], (p m, + ) s 1 s 3 s 2 s 4 s 5 99

100 Segment Tree Balanced binary search tree 단말노드 매기본구간마다대응하는단말노드를만든다. 모든단말노드는하나의기본구간을갖는다. 내부노드 그노드를 root 로하는모든단말노드에대응하는기본구간의합집합에해당하는 interval 을가진다 즉, 어떤내부노드에대응하는 interval 은그노드의두자식노드에대응하는 interval 의합집합이다. 루트노드에대응하는 interval 은 1 차원전체구간이된다. 각노드 v 에저장하는정보 Int(v): 노드 v 에대응하는 interval I 에속하는 interval 중에서 Int(v) [a, b] 이며 Int(parent(v)) [a, b] 를만족하는모든 interval [a, b] 들을리스트로 v 에저장 100

101 s 5 s 2, s 5 s 1 s 1 s 1 s 3 s 3, s 4 s 2, s 5 s 3 s 4 s 1 s 3 s 2 s 4 s 5 Space complexity : O(n log n) Time complexity : O(n log n) 101

102 IntervalPointQuery(T, q) : query point q 를포함하는모든 interval 을찾아서출력 IntervalPointQuerySegmentTree(v, qx) Report all intervals stored at v if (v is not a leaf) if (qx Int(v->left)) QuerySegmentTree(v->left, qx); else QuerySegmentTree(v->right, qx); Time complexity : O(log n + k) k : 출력되는구간의수 102

103 Insertion InsertSegmentTree(v, a, b) // interval [a,b] if Int(v) [a,b] store [a,b] at v; else if Int(v->left) [a,b] InsertSegmentTree(v->left, a, b); if Int(v->right) [a,b] InsertSegmentTree(v->right, a, b); Deletion Time complexity : O(log n) 103

104 R 3 R R

105

106 1 차원 Query ( 배열 a[max] 에서 ) Update a[i] Query q i p a [ i] (0 p q MAX ) 2 차원 Query ( 배열 a[max][max] 에서 ) Update a[i][j] Query r 2 ir 1 c 2 jc a[ i][ j] (0 r1 r2 MAX, 0 c1 c2 1 MAX ) 106

107 Binary Indexed Tree: 1 부터 2 K 까지의자연수를아래와같은계층적그룹으로 나눈구조트리 그룹 (Group) 그룹대표

108 Given an input array a[max], Define tree[ ] to store the sum of the group members! tree[ i] a[ k] ks ( i) tree[i] i a[i]

109 tree[ i] k S ( i) a[ k] tree[16] tree[ 16] 16 k1 a[ k] a[16] tree[15] tree[14] tree[12] tree[8] tree[i] i a[i]

110 C[ k] k i1 a[ i] C[13] 13 i1 13 (1101) C[13] tree[(1000) tree[8] tree[12] tree[13] 8 i1 a[ i] 2 a[ i] 12 i9 2 ] tree[(1100) a[ i] 13 i13 a[ i] 2 ] tree[(1101) 22 2 ] tree[i] i a[i]

111 q i p a[ i] C[ q] C[ p 1] a[ k] C[ k] C[ k 1] 111

112 a[k] a[k] value tree[i] i a[i]

113 Operations 어떤멤버의 index 로부터내가속하는모든그룹의그룹대표번호를어떻게구할것인가? 역시 index 연산으로가능 그룹 (Group) 그룹대표

114 그룹 (Group) 그룹대표 BIT(tree[]) 에서 임의의수 k : 반드시하나의그룹대표 그룹 : S(k) = {k-2 l(k) +1,, k}, (l(k) : k 의 last bit-1 위치 ) k = a1b = a1(00 00) S(k) = { a0(00 01), a0(00 10), a0(00 11),, a0(11 11), a1(00 00) } S(k) = 2 l(k) S(12) = S(1100) = {1001, 1010, 1011, 1100} = {9, 10, 11, 12} 114

115 Find Last bit-1 of a number N Given N = Return N & (-N), N & (N ^ (N-1)) Let & : AND, ^ : XOR N = a1b a = (0 1)*, b=0* N : complement of N Then, -N = (a1b) + 1 = a 0b + 1 = a 0(00 0) + 1 = a 0(11 1) + 1 = a 1(00 0) = a 1b N&(-N) = (a1b) & a 1b = (00 0)1(00 0) N&(N^(N-1)) = a1(00 0)&(a1(00 0)^a0(11 1)) = a1(00 0)&((00 0)1(11 1)) = (00 0)1(00 0) 115

116 Remove Last bit-1 of a number N Given N = Return N-N & (-N), N- N & (N ^ (N-1)) N&(N-1) Let N = a1b a = (0 1)*, b=0* & : AND, ^ : XOR Then, N&(N-1) = a1(00 0) & (a0(11 1)) = a0(00 0) 116

117 Cumulative Sum C[ k] k i1 a[ i] int tree[]; int getcumulativesum(int k) { int sum, index; sum = 0; index = k; while (index > 0) { sum += tree[index]; index -= GET_LAST_ONE(index); } return sum; } k = index = index = = = = = =

118 a[k] int tree[]; int size; a[k] value // size of tree void update(int k, int value) { int index; k = index = } index = k; while (index <= size) { tree[index] += value; index += GET_LAST_ONE(index);//add last significant bit } index = = = = = =

119 #define GET_LAST_ONE(N) ((N)^(-(N))) //#define GET_LAST_ONE(k) ((N)&((N)^((N)-1))) void initcumulativesum(int a[], int tree[], int size) { int i, sum, index; } int lastone, removelastone; for(i=1; i<=size; i++) { lastone = GET_LAST_ONE(i); removelastone = i - lastone; sum = a[i]; index = lastone-1; while (index > 0) { sum += tree[removelastone + index]; index -= GET_LAST_ONE(index); } } tree[i] = sum; Time complexity : O(n log n) i = lastone = removelastone = Index = Index = removelastone + index = = = = = = =

120 초기화 Step 1: 배열 a[][] 모든행에대하여 1 차원 BIT tree[][] 를만든다 주어진 1 차원배열에대하여그배열자체에 1 차원 BIT 를만들수있음에유의한다. Step 2: 모든행에대하여 1 차원 BIT 가만들어진배열 tree[][] 의모든열에대하여 1 차원 BIT 를만든다. 120

121 초기화

122 초기화이후 tree[][] 의값

123 Cumulative Sum C(p, q) p q i1j1 a[i][j] int tree[][]; int getcumsum2d(int p, int q) { int sum, index; sum = 0; for(i=p; i>0; i-=get_last_one(i)) for(j=q; j>0; j-=get_last_one(j)) sum += tree[i][j]; } return sum; } Query (Partial Cumulative Sum) p2 q 2 i p1j q 1 a[i][j] C(p,q ) C(p,q ) C(p 1,q ) C(p 1,q ) 123

124 Update a[p][q] a[p][q] value int tree[][]; int size_x, size_y; // size of tree void update(int p, int q, int value) { int ix, iy; ix = p; } while (ix <= size_x) { iy = q; while (iy <= size_y) { tree[ix][iy] += value; iy += GET_LAST_ONE(iY); } ix += GET_LAST_ONE(iX); } 124

125 초기화 #define GET_LAST_ONE(N) ((N)^(-(N))) //#define GET_LAST_ONE(k) ((N)&((N)^((N)-1))) void initcumsum2d(int a[][max], int tree[][max], int size) { int i, j, sum, index; int lastone, removelastone; for(i=1; i<=size; i++) { for(j=1; j<=size; j++) { lastone = GET_LAST_ONE (j); removelastone = j - lastone; sum = a[i][j]; index = lastone - 1; while(index > 0) { sum += a[i][removelastone + index]; index -= GET_LAST_ONE (index); } tree[i][j] = sum; } for(j=1; j<=size; j++) { lastone = GET_LAST_ONE (i); removelastone = i - lastone; sum = tree[i][j]; index = lastone - 1; while(index > 0) { sum += tree[removelastone + index][j]; index -= GET_LAST_ONE (index); } tree[i][j] = sum; } } } 125

126 Static&d1=tutorials&d2=binaryIndexedTrees