-
Notifications
You must be signed in to change notification settings - Fork 30
/
PersistentArraySqrt.ts
156 lines (138 loc) · 4.3 KB
/
PersistentArraySqrt.ts
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/* eslint-disable no-param-reassign */
//
// Persistent Array (sqrt decomposition)
//
// Description:
// An array with O(sqrt(n)) operations (inc. copy)
//
// Algorithm:
// Store base aray and operation sequence.
// If the length of operation sequence exceeds sqrt(n),
// update base array and clear the operation sequence.
//
// Complexity:
// Copy O(sqrt(n))
// Get O(sqrt(n))
// Set O(sqrt(n)) time and space per operation
//
// Comment:
// This implementation is much faster than the implementation
// based on a complete binary tree representation,
// which runs in O(log n) time / extra space per operation.
// 非常通用的实现:
// 1. 记录每个版本的修改:[index,value,version]
// 2. 查询时,从最新版本开始,找到最近的修改,返回修改后的值.
// 3. 更新时,如果修改的数量超过了2*sqrt(n),就更新基础数组并清空操作序列,保证修改的记录不会太长.
// !整体的时间复杂度是O(sqrt(n)).
/**
* 基于分块的完全可持久化数组.
*/
class PersistentArraySqrt<T> {
private _arr: ArrayLike<T>
private _opIndex: number[] = []
private _opValue: T[] = []
private _opVersion = 0
constructor(nOrNums: number | ArrayLike<T>) {
if (typeof nOrNums === 'number') {
nOrNums = Array(nOrNums)
}
this._arr = nOrNums
}
get(i: number): T | undefined {
// 查询上一个修改操作
for (let j = this._opVersion - 1; ~j; j--) {
if (this._opIndex[j] === i) {
return this._opValue[j]
}
}
return this._arr[i]
}
set(i: number, v: T): PersistentArraySqrt<T> {
this._opIndex.push(i)
this._opValue.push(v)
const n = this._arr.length
if (this._opIndex.length * this._opIndex.length <= 4 * n) {
return this._update()
}
// !如果操作序列的长度超过了2*sqrt(n),就更新基础数组并清空操作序列.
const newArr = new Array(n)
for (let j = 0; j < n; j++) {
newArr[j] = this._arr[j]
}
this._opIndex.forEach((v, i) => {
newArr[v] = this._opValue[i]
})
return new PersistentArraySqrt(newArr)
}
private _update(): PersistentArraySqrt<T> {
const copy = new PersistentArraySqrt(this._arr)
copy._opIndex = this._opIndex
copy._opValue = this._opValue
copy._opVersion = this._opVersion + 1
return copy
}
}
class PersistentArraySqrtInt32 {
private _arr: Int32Array
private _opIndex: number[] = []
private _opValue: number[] = []
private _opVersion = 0
constructor(nOrNums: number | Int32Array) {
if (typeof nOrNums === 'number') {
nOrNums = new Int32Array(nOrNums)
}
this._arr = nOrNums
}
get(i: number): number | undefined {
for (let j = this._opVersion - 1; ~j; j--) {
if (this._opIndex[j] === i) {
return this._opValue[j]
}
}
return this._arr[i]
}
set(i: number, v: number): PersistentArraySqrtInt32 {
this._opIndex.push(i)
this._opValue.push(v)
const n = this._arr.length
if (this._opIndex.length * this._opIndex.length <= 4 * n) {
return this._update()
}
const newArr = new Int32Array(n)
for (let j = 0; j < n; j++) {
newArr[j] = this._arr[j]
}
this._opIndex.forEach((v, i) => {
newArr[v] = this._opValue[i]
})
return new PersistentArraySqrtInt32(newArr)
}
private _update(): PersistentArraySqrtInt32 {
const copy = new PersistentArraySqrtInt32(this._arr)
copy._opIndex = this._opIndex
copy._opValue = this._opValue
copy._opVersion = this._opVersion + 1
return copy
}
}
export { PersistentArraySqrt, PersistentArraySqrtInt32 }
if (require.main === module) {
// https://leetcode.cn/problems/snapshot-array/
class SnapshotArray {
private readonly _gits: PersistentArraySqrtInt32[] = []
private _root: PersistentArraySqrtInt32
constructor(length: number) {
this._root = new PersistentArraySqrtInt32(length)
}
set(index: number, val: number): void {
this._root = this._root.set(index, val)
}
snap(): number {
this._gits.push(this._root)
return this._gits.length - 1
}
get(index: number, snapId: number): number {
return this._gits[snapId].get(index)!
}
}
}