我正在学习线段树，遇到了这个问题。
有一个数组 A 和两种操作类型
1. Find the Sum in Range L to R
2. Update the Element in Range L to R by Value X.
更新应该像这样。
A[L] = 1*X;
A[L+1] = 2*X;
A[L+2] = 3*X;
A[R] = (R-L+1)*X;
我应该如何处理第二种查询？请问有没有一些修改线段树算法的方法，或者有更好的解决方案。
线段树的更新操作
9
更新应该像这样。
- DreamWorks
3
你的问题中有更新查询的限制吗？我的意思是可能会给出多少个更新查询？ - Kaidul
@KaidulIslam，Q 的范围在 0 到 10^5 之间。 - DreamWorks
看起来懒惰传播是可能的，但需要一些额外的复杂性和空间。此外，逐个更新每个数组索引也是可能的，但效率非常低下。 - Kaidul
3个回答
9
因此，需要高效地将区间
为了高效解决这个问题，让我们利用具有懒惰传播的线段树。
基本思路如下：
提供的解决方案中，线段树是使用对象和引用来实现的，但可以很容易地修改为使用数组。
[L，R] 更新为以步长 X 的算术级数对应的值，并能够高效地找到不同区间的总和。为了高效解决这个问题，让我们利用具有懒惰传播的线段树。
基本思路如下：
可以通过
第一个和最后一个项以及项数来定义算数级数。通过组合两个不同的算术级数（具有相同的项数）的
第一个和最后一个项，可以获得新的算术级数。新算术级数的第一个和最后一个项将仅是组合的相应项的组合因此，我们可以将与给定区间上跨越的算术级数的
第一个和最后一个值相关联的每个线段树节点在更新期间，对于所有受影响的区间，我们可以通过线段树懒惰地传播
第一个和最后一个项的值，并更新这些区间上的聚合总和。
class Node {
int left; // Left boundary of the current SegmentTree node
int right; // Right boundary of the current SegmentTree node
int sum; // Sum on the interval [left,right]
int first; // First item of arithmetic progression inside given node
int last; // Last item of arithmetic progression
Node left_child;
Node right_child;
// Constructor
Node(int[] arr, int l, int r) { ... }
// Add arithmetic progression with step X on the interval [l,r]
// O(log(N))
void add(int l, int r, int X) { ... }
// Request the sum on the interval [l,r]
// O(log(N))
int query(int l, int r) { ... }
// Lazy Propagation
// O(1)
void propagate() { ... }
}
可以看到，在Lazy Propagation期间，更新子节点算术进展的first和last项目，同时还会更新父节点中的sum。
实现
以下是所描述方法的Java实现（带有附加注释）:
class Node {
int left; // Left boundary of the current SegmentTree node
int right; // Right boundary of the current SegmentTree node
int sum; // Sum on the interval
int first; // First item of arithmetic progression
int last; // Last item of arithmetic progression
Node left_child;
Node right_child;
/**
* Construction of a Segment Tree
* which spans over the interval [l,r]
*/
Node(int[] arr, int l, int r) {
left = l;
right = r;
if (l == r) { // Leaf
sum = arr[l];
} else { // Construct children
int m = (l + r) / 2;
left_child = new Node(arr, l, m);
right_child = new Node(arr, m + 1, r);
// Update accumulated sum
sum = left_child.sum + right_child.sum;
}
}
/**
* Lazily adds the values of the arithmetic progression
* with step X on the interval [l, r]
* O(log(N))
*/
void add(int l, int r, int X) {
// Lazy propagation
propagate();
if ((r < left) || (right < l)) {
// If updated interval doesn't overlap with current subtree
return;
} else if ((l <= left) && (right <= r)) {
// If updated interval fully covers the current subtree
// Update the first and last items of the arithmetic progression
int first_item_offset = (left - l) + 1;
int last_item_offset = (right - l) + 1;
first = X * first_item_offset;
last = X * last_item_offset;
// Lazy propagation
propagate();
} else {
// If updated interval partially overlaps with current subtree
left_child.add(l, r, X);
right_child.add(l, r, X);
// Update accumulated sum
sum = left_child.sum + right_child.sum;
}
}
/**
* Returns the sum on the interval [l, r]
* O(log(N))
*/
int query(int l, int r) {
// Lazy propagation
propagate();
if ((r < left) || (right < l)) {
// If requested interval doesn't overlap with current subtree
return 0;
} else if ((l <= left) && (right <= r)) {
// If requested interval fully covers the current subtree
return sum;
} else {
// If requested interval partially overlaps with current subtree
return left_child.query(l, r) + right_child.query(l, r);
}
}
/**
* Lazy propagation
* O(1)
*/
void propagate() {
// Update the accumulated value
// with the sum of Arithmetic Progression
int items_count = (right - left) + 1;
sum += ((first + last) * items_count) / 2;
if (right != left) { // Current node is not a leaf
// Calculate the step of the Arithmetic Progression of the current node
int step = (last - first) / (items_count - 1);
// Update the first and last items of the arithmetic progression
// inside the left and right subtrees
// Distribute the arithmetic progression between child nodes
// [a(1) to a(N)] -> [a(1) to a(N/2)] and [a(N/2+1) to a(N)]
int mid = (items_count - 1) / 2;
left_child.first += first;
left_child.last += first + (step * mid);
right_child.first += first + (step * (mid + 1));
right_child.last += last;
}
// Reset the arithmetic progression of the current node
first = 0;
last = 0;
}
}
提供的解决方案中，线段树是使用对象和引用来实现的，但可以很容易地修改为使用数组。
测试
以下提供随机测试，比较了两种实现方式：
- 将数组每个项逐一增加进行查询处理，时间复杂度为 O(N) ，在区间上计算总和的时间复杂度也为 O(N)
- 使用时间复杂度为O(log(N)) 的线段树处理相同的查询：
随机测试的Java实现：
public static void main(String[] args) {
// Initialize the random generator with predefined seed,
// in order to make the test reproducible
Random rnd = new Random(1);
int test_cases_num = 20;
int max_arr_size = 100;
int num_queries = 50;
int max_progression_step = 20;
for (int test = 0; test < test_cases_num; test++) {
// Create array of the random length
int[] arr = new int[rnd.nextInt(max_arr_size) + 1];
Node segmentTree = new Node(arr, 0, arr.length - 1);
for (int query = 0; query < num_queries; query++) {
if (rnd.nextDouble() < 0.5) {
// Update on interval [l,r]
int l = rnd.nextInt(arr.length);
int r = rnd.nextInt(arr.length - l) + l;
int X = rnd.nextInt(max_progression_step);
update_sequential(arr, l, r, X); // O(N)
segmentTree.add(l, r, X); // O(log(N))
}
else {
// Request sum on interval [l,r]
int l = rnd.nextInt(arr.length);
int r = rnd.nextInt(arr.length - l) + l;
int expected = query_sequential(arr, l, r); // O(N)
int actual = segmentTree.query(l, r); // O(log(N))
if (expected != actual) {
throw new RuntimeException("Results are different!");
}
}
}
}
System.out.println("All results are equal!");
}
static void update_sequential(int[] arr, int left, int right, int X) {
for (int i = left; i <= right; i++) {
arr[i] += X * ((i - left) + 1);
}
}
static int query_sequential(int[] arr, int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += arr[i];
}
return sum;
}
- stemm
1
如果将其更改为“查找范围L到R内的乘积”，会怎样？ - DreamWorks
0
第二个操作可以被视为向区间[L，R]添加一个线段，该线段具有两个端点（L，x），（R，（R-L + 1）* x）和斜率1。
关于带有区间修改的线段树，最重要的考虑因素是懒惰标记是否可以合并。如果我们将修改视为添加线段，则可以发现两个线段可以轻松合并-我们只需要更新斜率和端点即可。对于每个区间，我们只需要维护此区间的线段的斜率和起点。通过使用懒惰标记技术，我们可以在O（nlogn）时间复杂度内轻松实现查询区间和和进行区间修改。
- starling
0
基本上你需要建立一棵树，然后使用惰性传播进行更新，这里是实现方法。
int tree[1 << 20], Base = 1 << 19;
int lazy[1 << 20];
void propagation(int v){ //standard propagation
tree[v * 2] += lazy[v];
tree[v * 2 + 1] += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] == 0;
}
void update(int a, int b, int c, int v = 1, int p = 1, int k = Base){
if(p > b || k < a) return; //if outside range [a, b]
propagation(v);
if(p >= a && k <= b){ // if fully inside range [a, b]
tree[v] += c;
lazy[v] += c;
return;
}
update(a, b, c, v * 2, p, (p + k) / 2); //left child
update(a, b, c, v * 2 + 1, (p + k) / 2 + 1, k); //right child
tree[v] = tree[v * 2] + tree[v * 2 + 1]; //update current node
}
int query(int a, int b, int v = 1, int p = 1, int k = Base){
if(p > b || k < a) //if outside range [a, b]
return 0;
propagation(v);
if(p >= a && k <= b) // if fully inside range [a, b]
return tree[v];
int res = 0;
res += query(a, b, c, v * 2, p, (p + k) / 2); //left child
res += query(a, b, c, v * 2 + 1, (p + k) / 2 + 1, k); //right child
tree[v] = tree[v * 2] + tree[v * 2 + 1]; //update current node
return res;
}
update函数显然会更新树，因此它会在区间[a, b]（或[L, R]）上添加两个节点。
update(L, R, value);
查询函数只会给你返回范围内元素的总和
query(L, R);
- noobgotbanned
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接