-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsegtree.html
111 lines (77 loc) · 3.26 KB
/
segtree.html
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
<!DOCTYPE html>
<html>
<script src="segtree.js"></script>
<head>
<meta charset="utf-8">
<link rel="stylesheet" href="style.css">
<title>
Segment Tree
</title>
</head>
<body onload="initall()">
<div class="holdall">
<div class="sdiv" id="lsdiv">
<div class="maindiv">
<svg id=stvis width="512" height="512"></svg>
</div>
<div class="maindiv" id="outputText">
</div>
<div id="controls" class="uidiv">
<div class="controlcontainer">
<input type="number" id="linput" placeholder="Left bound of query">
<input type="number" id="rinput" placeholder="Right bound of query">
<button onclick="UserInteraction.queryOperation()">Go</button>
</div>
<div class="controlcontainer">
<input type="number" id="valueInput" placeholder="Value to add">
<input type="number" id="indexInput" placeholder="Index to add to">
<button onclick="UserInteraction.updateOperation()">Go</button>
</div>
</div>
</div>
<div class="resizer" id="resizer"></div>
<div class="rres" id="outputText2">
<div>
<h2>
About
</h2>
<p>
You are given an array, and you should be able to modify elements and find the sum of a range in the array. Segment trees accomplish this in logarithmic time per operation by breaking the array into segments of size 1, 2, 4, 8, etc.
</p>
<p>
The segment tree can also be extended to support a wide variety of operations, such as range updates, multiple different types of update operations (add, set, multiply, all at the same time), and higher-dimensional segment trees.
</p>
<hr>
<h2>
Updating
</h2>
<p>
Update operations: there are at most lg(N) nodes that cover one index. Traversing the tree from the element at the bottom up to the top and updating each node along the way will be enough to update.
</p>
<p>
Start at the bottom by adding a constant to the index being added to. To find the parent of a node with index i, take (i - 1) / 2, rounding down. Repeat until node 0 is reached. In this example, 1 is added to the node with index 3.
</p>
<p class="maindiv">
<b onclick="UserInteraction.updopsteps(1, 3, 1)">Step 1</b>
<b onclick="UserInteraction.updopsteps(2, 3, 1)">Step 2</b>
<b onclick="UserInteraction.updopsteps(3, 3, 1)">Step 3</b>
<b onclick="UserInteraction.updopsteps(4, 3, 1)">Step 4</b>
</p>
<p id="updinfotxt" class="maindiv"></p>
<div class='maindiv'><svg id=uexsvg width='256' height='256'></svg></div>
<hr>
<h2>
Querying
</h2>
<p>
Query operations: because of the way the tree is organized, each range is split into at most 2 segments of each length, so at most 2 * lg(N) nodes are added together.
</p>
<p>
Any segment can be represented as a sequence of segments of length one. First, merge adjacent elements into segments of length two. Doing this will leave at most 2 segments of length one. Repeat the process for segments of length two (ignoring the segments of length one now), all the way up to segments of length n. This will leave at most 2 segments of each length to query.
</p>
<div class='maindiv'><svg id=qexsvg width='256' height='256'></svg></div>
</div>
</div>
</div>
</body>
</html>