更新线段树
Update in Segment Tree
我正在学习线段树，我遇到了这个问题。
有数组A和2种操作
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;
我应该如何处理第二种类型的查询 谁能提供一些算法来修改线段树，或者有更好的解决方案
因此，需要有效更新区间[L,R]为等差数列对应的值X，并使能够有效地找到不同区间的总和。
为了有效地解决这个问题 - 让我们使用 具有惰性传播的线段树。
基本思路如下：
等差数列可以由first和last项和amount of items
两个不同等差数列的first和last项组合可以得到一个新的等差数列 （具有相同数量的项目）。新等差数列的first和last项只是组合等差数列相应项的组合
因此，我们可以关联线段树的每个节点——等差级数的first和last值，它跨越给定的区间
在更新期间，对于所有受影响的区间，我们可以通过线段树延迟传播 - first 和 last 项的值，并更新聚合总和这些间隔。
因此，给定问题的线段树节点将具有以下结构：
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() { ... }
}
具有惰性传播的线段树的特殊性在于，每次遍历树的节点时 - 惰性传播例程（其复杂度为 O( 1)) 对给定节点执行。 因此，下面提供了一些任意节点的惰性传播逻辑的说明，该节点具有子节点：
可以看到，在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)[=81] 计算间隔总和=]
- 使用具有 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;
}
基本上你需要做一棵树，然后使用惰性传播进行更新，这里是实现。
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;
}
更新函数显然会更新树，因此它会添加到区间 [a, b]（或 [L, R]）上的节点
update(L, R, value);
查询函数只给出范围内元素的总和
query(L, R);
第二个操作可以看成是在区间[L,R]上加一段，两端点为(L,x),(R,(R-L+1)*x)，斜率为1.
区间修改的线段树最需要考虑的是是否可以合并惰性标签。如果我们将修改视为添加段，我们可以发现两个段可以很容易地合并——我们只需要更新斜率和端点。对于每个区间，我们只需要维护这个区间的斜率和线段起点。通过使用惰性标记技术，我们可以很容易地实现O(nlogn)时间复杂度的查询区间求和和区间修改。
我正在学习线段树，我遇到了这个问题。
有数组A和2种操作
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;
我应该如何处理第二种类型的查询 谁能提供一些算法来修改线段树，或者有更好的解决方案
因此，需要有效更新区间[L,R]为等差数列对应的值X，并使能够有效地找到不同区间的总和。
为了有效地解决这个问题 - 让我们使用 具有惰性传播的线段树。
基本思路如下：
等差数列可以由
first和last项和amount of items项定义
两个不同等差数列的
first和last项组合可以得到一个新的等差数列 （具有相同数量的项目）。新等差数列的first和last项只是组合等差数列相应项的组合因此，我们可以关联线段树的每个节点——等差级数的
first和last值，它跨越给定的区间在更新期间，对于所有受影响的区间，我们可以通过线段树延迟传播 -
first和last项的值，并更新聚合总和这些间隔。
因此，给定问题的线段树节点将具有以下结构：
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() { ... }
}
具有惰性传播的线段树的特殊性在于，每次遍历树的节点时 - 惰性传播例程（其复杂度为 O( 1)) 对给定节点执行。 因此，下面提供了一些任意节点的惰性传播逻辑的说明，该节点具有子节点：
可以看到，在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)[=81] 计算间隔总和=]
- 使用具有 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;
}
基本上你需要做一棵树，然后使用惰性传播进行更新，这里是实现。
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;
}
更新函数显然会更新树，因此它会添加到区间 [a, b]（或 [L, R]）上的节点
update(L, R, value);
查询函数只给出范围内元素的总和
query(L, R);
第二个操作可以看成是在区间[L,R]上加一段，两端点为(L,x),(R,(R-L+1)*x)，斜率为1.
区间修改的线段树最需要考虑的是是否可以合并惰性标签。如果我们将修改视为添加段，我们可以发现两个段可以很容易地合并——我们只需要更新斜率和端点。对于每个区间，我们只需要维护这个区间的斜率和线段起点。通过使用惰性标记技术，我们可以很容易地实现O(nlogn)时间复杂度的查询区间求和和区间修改。