假设你有一个长度为 n 的数组,初始情况下所有的数字均为 0,你将会被给出 k 个更新的操作。
其中,每个操作会被表示为一个三元组:[startIndex, endIndex, inc],你需要将子数组 A[startIndex ... endIndex](包括 startIndex 和 endIndex)增加 inc。
请你返回 k 次操作后的数组。
示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] 输出: [-2,0,3,5,3]
解释:
初始状态: [0,0,0,0,0] 进行了操作 [1,3,2] 后的状态: [0,2,2,2,0] 进行了操作 [2,4,3] 后的状态: [0,2,5,5,3] 进行了操作 [0,2,-2] 后的状态: [-2,0,3,5,3]
差分数组模板题。
我们定义
时间复杂度
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
d = [0] * length
for l, r, c in updates:
d[l] += c
if r + 1 < length:
d[r + 1] -= c
return list(accumulate(d))
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] d = new int[length];
for (var e : updates) {
int l = e[0], r = e[1], c = e[2];
d[l] += c;
if (r + 1 < length) {
d[r + 1] -= c;
}
}
for (int i = 1; i < length; ++i) {
d[i] += d[i - 1];
}
return d;
}
}
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> d(length);
for (auto& e : updates) {
int l = e[0], r = e[1], c = e[2];
d[l] += c;
if (r + 1 < length) d[r + 1] -= c;
}
for (int i = 1; i < length; ++i) d[i] += d[i - 1];
return d;
}
};
func getModifiedArray(length int, updates [][]int) []int {
d := make([]int, length)
for _, e := range updates {
l, r, c := e[0], e[1], e[2]
d[l] += c
if r+1 < length {
d[r+1] -= c
}
}
for i := 1; i < length; i++ {
d[i] += d[i-1]
}
return d
}
/**
* @param {number} length
* @param {number[][]} updates
* @return {number[]}
*/
var getModifiedArray = function (length, updates) {
const d = new Array(length).fill(0);
for (const [l, r, c] of updates) {
d[l] += c;
if (r + 1 < length) {
d[r + 1] -= c;
}
}
for (let i = 1; i < length; ++i) {
d[i] += d[i - 1];
}
return d;
};
时间复杂度
树状数组,也称作“二叉索引树”(Binary Indexed Tree)或 Fenwick 树。 它可以高效地实现如下两个操作:
-
单点更新
update(x, delta)
: 把序列$x$ 位置的数加上一个值$delta$ ; -
前缀和查询
query(x)
:查询序列$[1,...x]$ 区间的区间和,即位置$x$ 的前缀和。
这两个操作的时间复杂度均为
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
tree = BinaryIndexedTree(length)
for start, end, inc in updates:
tree.update(start + 1, inc)
tree.update(end + 2, -inc)
return [tree.query(i + 1) for i in range(length)]
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
BinaryIndexedTree tree = new BinaryIndexedTree(length);
for (int[] e : updates) {
int start = e[0], end = e[1], inc = e[2];
tree.update(start + 1, inc);
tree.update(end + 2, -inc);
}
int[] ans = new int[length];
for (int i = 0; i < length; ++i) {
ans[i] = tree.query(i + 1);
}
return ans;
}
}
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += lowbit(x);
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}
public static int lowbit(int x) {
return x & -x;
}
}
class BinaryIndexedTree {
public:
int n;
vector<int> c;
BinaryIndexedTree(int _n)
: n(_n)
, c(_n + 1) {}
void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += lowbit(x);
}
}
int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= lowbit(x);
}
return s;
}
int lowbit(int x) {
return x & -x;
}
};
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
BinaryIndexedTree* tree = new BinaryIndexedTree(length);
for (auto& e : updates) {
int start = e[0], end = e[1], inc = e[2];
tree->update(start + 1, inc);
tree->update(end + 2, -inc);
}
vector<int> ans;
for (int i = 0; i < length; ++i) ans.push_back(tree->query(i + 1));
return ans;
}
};
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}
func getModifiedArray(length int, updates [][]int) []int {
tree := newBinaryIndexedTree(length)
for _, e := range updates {
start, end, inc := e[0], e[1], e[2]
tree.update(start+1, inc)
tree.update(end+2, -inc)
}
ans := make([]int, length)
for i := range ans {
ans[i] = tree.query(i + 1)
}
return ans
}