FilesExpand file tree

master

/

SegmentTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

135 lines (105 loc) · 3.82 KB

master

/

SegmentTree.java

Copy path

Top

File metadata and controls

• Code
• Blame

135 lines (105 loc) · 3.82 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

package Query;

public class SegmentTree<E> {

private E[] tree;

private E[] data;

private Merger<E> merger;

public SegmentTree(E[] arr, Merger<E> merger) {

this.merger = merger;

data = (E[]) new Object[arr.length];

for (int i = 0; i < arr.length; i++) {

data[i] = arr[i];

}

tree = (E[]) new Object[4 * arr.length];

buildSegmentTree(0, 0, data.length - 1);

}

private void buildSegmentTree(int treeIndex, int l, int r) {

if (l == r) {

tree[treeIndex] = data[l];//tree[treeIndex] = data[r];

return;

}

int leftChild = leftChild(treeIndex);

int rightChild = rightChild(treeIndex);

int mid = l + (r - l) / 2;

buildSegmentTree(leftChild, l, mid);

buildSegmentTree(rightChild, mid + 1, r);

tree[treeIndex] = merger.merger(tree[leftChild], tree[rightChild]);

}

public int getSize() {

return data.length;

}

public E get(int index) {

if (index < 0 || index >= data.length) {

throw new IllegalArgumentException("the index is error");

}

return data[index];

}

private int leftChild(int index) {

if (index < 0 || index >= data.length) {

throw new IllegalArgumentException("the index is error");

}

return 2 * index + 1;

}

private int rightChild(int index) {

if (index < 0 || index >= data.length) {

throw new IllegalArgumentException("the index is error");

}

return 2 * index + 2;

}

public E query(int queryL, int queryR) {

if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length)

throw new IllegalArgumentException("the index is error");

return query(0, 0, data.length - 1, queryL, queryR);

}

//在treeIndex为根的线段树[l,r]中，搜索queryL与queryR的值

private E query(int treeIndex, int l, int r, int queryL, int queryR) {

if (l == queryL && r == queryR)

return tree[treeIndex];

int mid = l + (r - l) / 2;

//treeIndex的结点分为[l..mid]与[mid+1,r]

int leftTreeIndex = leftChild(treeIndex);

int rightTreeIndex = rightChild(treeIndex);

if (queryL >= mid + 1)

return query(rightTreeIndex, mid + 1, r, queryL, queryR);

else if (queryR <= mid)

return query(leftTreeIndex, l, mid, queryL, queryR);

E lefResult = query(leftTreeIndex, l, mid, queryL, mid);

E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);

return merger.merger(lefResult, rightResult);

}

public void set(int index, E e) {

if (index < 0 || index >= data.length) {

throw new IllegalArgumentException("the index is error");

}

data[index] = e;

set(0, 0, data.length - 1, index, e);

}

private void set(int treeIndex, int l, int r, int index, E e) {

if (l == r) {

tree[treeIndex] = e;

return;

}

int leftTreeIndex = leftChild(treeIndex);

int rightTreeIndex = rightChild(treeIndex);

int mid = l + (r - l) / 2;

if (index >= mid + 1)

set(rightTreeIndex, mid + 1, r, index, e);

else

set(leftTreeIndex, l, mid, index, e);

tree[treeIndex] = merger.merger(tree[leftTreeIndex], tree[rightTreeIndex]);

}

@Override

public String toString() {

StringBuilder res = new StringBuilder();

res.append('[');

for (int i = 0; i < tree.length; i++) {

if (tree[i] != null)

res.append(tree[i]);

else

res.append("null");

if (i != tree.length - 1)

res.append(", ");

}

res.append(']');

return res.toString();

}

}