Skip to content

Commit 9f7f863

Browse files
taokexiataokexia
committed
add segmenttree
1 parent d9b13e1 commit 9f7f863

4 files changed

Lines changed: 208 additions & 0 deletions

File tree

‎JavaScript/SegmentTree/SegmentTree.js‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
// 线段树
2+
module.exports = class SegmentTree {
3+
constructor(data, merge) {
4+
this.data = data;
5+
this.tree = [];
6+
// 指定节点的合并业务
7+
this.merge = merge;
8+
this.buildSegmentTree(0, 0, data.length-1);
9+
}
10+
// 在treeIndex的位置创建表示区间[l...r]的线段树
11+
buildSegmentTree(treeIndex, l, r) {
12+
if(l === r) {
13+
this.tree[treeIndex] = this.data[l];
14+
return;
15+
}
16+
let leftTreeIndex = this.leftChild(treeIndex);
17+
let rightTreeIndex = this.rightChild(treeIndex);
18+
19+
let mid = l + Math.floor((r - l)/2);
20+
this.buildSegmentTree(leftTreeIndex, l, mid);
21+
this.buildSegmentTree(rightTreeIndex, mid+1, r);
22+
this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex]);
23+
}
24+
// 返回区间[queryL, queryR]的值
25+
query(queryL, queryR) {
26+
if(queryL < 0 || queryL >= this.data.length || queryR < 0 || queryR >= this.data.length || queryL > queryR)
27+
return;
28+
return this.__query(0, 0, this.data.length-1, queryL, queryR);
29+
}
30+
// 在以treeIndex为根的线段树中[l...r]的范围里，搜索区间[queryL, queryR]的值
31+
__query(treeIndex, l, r, queryL, queryR) {
32+
// 节点左边界和右边界都与想要查找的重合
33+
if(l === queryL && r === queryR)
34+
return this.tree[treeIndex];
35+
let mid = l + Math.floor((r-l)/2);
36+
37+
// 以treeIndex的节点为[l...mid]和[mid+1...r]两部分
38+
let leftTreeIndex = this.leftChild(treeIndex);
39+
let rightTreeIndex = this.rightChild(treeIndex);
40+
// 用户关注的区间和左孩子一点关系没有
41+
if(queryL >= mid+1) {
42+
// 去右子树查找
43+
return this.__query(rightTreeIndex, mid+1, r, queryL, queryR);
44+
}
45+
else if(queryR <= mid) {
46+
// 用户关注区间和右边没有关系
47+
return this.__query(leftTreeIndex, l, mid, queryL, queryR);
48+
}
49+
// 一部分左，一部分右 queryL R 被一份为二
50+
let leftResult = this.__query(leftTreeIndex, l, mid, queryL, mid);
51+
let rightResult = this.__query(rightTreeIndex, mid+1, r, mid+1, queryR);
52+
return this.merge(leftResult, rightResult);
53+
}
54+
// 遍历打印树中节点中值信息
55+
toString() {
56+
let res = "[";
57+
for(let i = 0;i < this.tree.length;i++) {
58+
if(this.tree[i] !== undefined)
59+
res += this.tree[i];
60+
else
61+
res += "null";
62+
63+
if(i != this.tree.length-1) {
64+
res += ", ";
65+
}
66+
}
67+
res += "]";
68+
return res;
69+
}
70+
// 获得线段树的长度
71+
getSize() {
72+
return this.data.length;
73+
}
74+
// 获得索引所对应的值
75+
get(index) {
76+
return this.data[index];
77+
}
78+
// 线段树的更新操作
79+
// 将index位置的值，更新为e
80+
set(index, e) {
81+
this.data[index] = e;
82+
this.__set(0, 0, this.data.length-1, index, e);
83+
}
84+
// 在以treeIndex为根的线段树中更新index的值为e
85+
__set(treeIndex, l, r, index, e) {
86+
if(l === r) {
87+
this.tree[treeIndex] = e;
88+
return;
89+
}
90+
// 找到index所对应的叶子
91+
let mid = l + Math.floor((r-l)/2);
92+
// 以treeIndex的节点为[l...mid]和[mid+1...r]两部分
93+
let leftTreeIndex = this.leftChild(treeIndex);
94+
let rightTreeIndex = this.rightChild(treeIndex);
95+
if(index >= mid+1)
96+
this.__set(rightTreeIndex, mid+1, r, index, e);
97+
else // index <= mid
98+
this.__set(leftTreeIndex, l, mid, index, e);
99+
this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex]);
100+
}
101+
// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
102+
leftChild(index) {
103+
return 2*index+1;
104+
}
105+
// 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
106+
rightChild(index) {
107+
return 2*index+2;
108+
}
109+
}

‎JavaScript/SegmentTree/SegmentTreeII.js‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
// 线段树II
2+
// 递归实现线段树
3+
module.exports = class SegmentTree{
4+
constructor(nums, merge) {
5+
this.data = nums;
6+
// 指定节点的合并业务
7+
this.merge = merge;
8+
this.tree = new Array(nums.length).fill(0);
9+
this.tree.push(...nums);
10+
// 生成线段树
11+
// 两个子节点对应为：i*2, i*2+1
12+
for(let i = nums.length-1; i > 0; i--) {
13+
this.tree[i] = merge(this.tree[2*i],this.tree[2*i+1]);
14+
}
15+
}
16+
// 遍历打印树中节点中值信息
17+
toString() {
18+
let res = "[";
19+
for(let i = 0;i < this.tree.length;i++) {
20+
if(this.tree[i] !== undefined)
21+
res += this.tree[i];
22+
else
23+
res += "null";
24+
25+
if(i != this.tree.length-1) {
26+
res += ", ";
27+
}
28+
}
29+
res += "]";
30+
return res;
31+
}
32+
// 线段树的更新操作
33+
// 将index位置的值，更新为e
34+
set(index, e) {
35+
index += this.data.length;
36+
let tree = this.tree;
37+
tree[index] = e;
38+
index = Math.floor(index / 2);
39+
while(index > 0) {
40+
// 更新父节点
41+
tree[index] = this.merge(tree[index*2],tree[index*2 + 1]);
42+
index = Math.floor(index/2);
43+
}
44+
}
45+
// 返回区间[queryL, queryR]的值
46+
query(l, r) {
47+
let ret = 0;
48+
let tree = this.tree;
49+
l += this.data.length;
50+
r += this.data.length;
51+
while(l <= r) {
52+
// 如果当前left区间是奇数，说明相对其父节点是右子节点(2*i+1)
53+
// 父节点中，左子节点是不在范围内的，所以不需要计算，要进行处理
54+
if(l % 2) {
55+
ret = this.merge(ret, tree[l]);
56+
l++;
57+
}
58+
// 如果当前right区间是偶数，说明相对其父节点是左子节点(2*i)
59+
// 父节点中，右子节点是不在范围内的，所以不需要计算，要进行处理
60+
if(!(r%2)) {
61+
ret = this.merge(ret, tree[r]);
62+
r--;
63+
}
64+
l = Math.floor(l/2);
65+
r = Math.floor(r/2);
66+
}
67+
return ret;
68+
}
69+
}
70+

‎JavaScript/SegmentTree/Test.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
// 测试线段树
2+
var SegmentTree = require('./SegmentTree');
3+
var nums = [-2, 0, 3, -5, 2, -1];
4+
var sg = new SegmentTree(nums, (a, b)=> a+b);
5+
console.log(sg.toString());
6+
console.log(sg.query(0, 2));
7+
console.log(sg.query(2, 5));
8+
console.log(sg.query(0, 5));
9+
sg.set(3, 4)
10+
console.log(sg.toString());
11+
console.log(sg.query(0, 5));
12+
13+
console.log("=============================测试线段树II===================================")
14+
var SegmentTreeII = require('./SegmentTreeII');
15+
var nums2 = [-2, 0, 3, -5, 2, -1];
16+
var sgi = new SegmentTreeII(nums2, (a, b)=> a+b);
17+
console.log(sgi.toString());
18+
console.log(sgi.query(0, 2));
19+
console.log(sgi.query(2, 5));
20+
console.log(sgi.query(0, 5));
21+
sgi.set(3, 4)
22+
console.log(sgi.toString());
23+
console.log(sgi.query(0, 5));

‎README.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,12 @@
3838
- [并查集IV](./JavaScript/UnionFind/UnionFindIV.js)
3939
- [并查集V](./JavaScript/UnionFind/UnionFindV.js)
4040

41+
### 线段树:
42+
一种树形结构，用于获取区间内数值操作的结果
43+
44+
- [线段树I](./JavaScript/SegmentTree/SegmentTree.js)
45+
- [线段树II](./JavaScript/SegmentTree/SegmentTreeII.js)
46+
4147
### 图论：
4248

4349
- [图的实现](./JavaScript/Graph/Graph.js)

0 commit comments

Comments
 (0)