You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
199 lines
4.4 KiB
199 lines
4.4 KiB
package class47;
|
|
|
|
// 同时支持范围增加 + 范围修改 + 范围查询的动态开点线段树(累加和)
|
|
// 真的用到!才去建立
|
|
// 懒更新,及其所有的东西,和普通线段树,没有任何区别!
|
|
public class Code02_DynamicSegmentTree {
|
|
|
|
public static class Node {
|
|
public int sum;
|
|
public int lazy;
|
|
public int change;
|
|
public boolean update;
|
|
public Node left;
|
|
public Node right;
|
|
}
|
|
|
|
public static class DynamicSegmentTree {
|
|
public Node root;
|
|
public int size;
|
|
|
|
public DynamicSegmentTree(int max) {
|
|
root = new Node();
|
|
size = max;
|
|
}
|
|
|
|
private void pushUp(Node c) {
|
|
c.sum = c.left.sum + c.right.sum;
|
|
}
|
|
|
|
private void pushDown(Node p, int ln, int rn) {
|
|
if (p.left == null) {
|
|
p.left = new Node();
|
|
}
|
|
if (p.right == null) {
|
|
p.right = new Node();
|
|
}
|
|
if (p.update) {
|
|
p.left.update = true;
|
|
p.right.update = true;
|
|
p.left.change = p.change;
|
|
p.right.change = p.change;
|
|
p.left.lazy = 0;
|
|
p.right.lazy = 0;
|
|
p.left.sum = p.change * ln;
|
|
p.right.sum = p.change * rn;
|
|
p.update = false;
|
|
}
|
|
if (p.lazy != 0) {
|
|
p.left.lazy += p.lazy;
|
|
p.right.lazy += p.lazy;
|
|
p.left.sum += p.lazy * ln;
|
|
p.right.sum += p.lazy * rn;
|
|
p.lazy = 0;
|
|
}
|
|
}
|
|
|
|
public void update(int s, int e, int v) {
|
|
update(root, 1, size, s, e, v);
|
|
}
|
|
|
|
private void update(Node c, int l, int r, int s, int e, int v) {
|
|
if (s <= l && r <= e) {
|
|
c.update = true;
|
|
c.change = v;
|
|
c.sum = v * (r - l + 1);
|
|
c.lazy = 0;
|
|
} else {
|
|
int mid = (l + r) >> 1;
|
|
pushDown(c, mid - l + 1, r - mid);
|
|
if (s <= mid) {
|
|
update(c.left, l, mid, s, e, v);
|
|
}
|
|
if (e > mid) {
|
|
update(c.right, mid + 1, r, s, e, v);
|
|
}
|
|
pushUp(c);
|
|
}
|
|
}
|
|
|
|
public void add(int s, int e, int v) {
|
|
add(root, 1, size, s, e, v);
|
|
}
|
|
|
|
private void add(Node c, int l, int r, int s, int e, int v) {
|
|
if (s <= l && r <= e) {
|
|
c.sum += v * (r - l + 1);
|
|
c.lazy += v;
|
|
} else {
|
|
int mid = (l + r) >> 1;
|
|
pushDown(c, mid - l + 1, r - mid);
|
|
if (s <= mid) {
|
|
add(c.left, l, mid, s, e, v);
|
|
}
|
|
if (e > mid) {
|
|
add(c.right, mid + 1, r, s, e, v);
|
|
}
|
|
pushUp(c);
|
|
}
|
|
}
|
|
|
|
public int query(int s, int e) {
|
|
return query(root, 1, size, s, e);
|
|
}
|
|
|
|
private int query(Node c, int l, int r, int s, int e) {
|
|
if (s <= l && r <= e) {
|
|
return c.sum;
|
|
}
|
|
int mid = (l + r) >> 1;
|
|
pushDown(c, mid - l + 1, r - mid);
|
|
int ans = 0;
|
|
if (s <= mid) {
|
|
ans += query(c.left, l, mid, s, e);
|
|
}
|
|
if (e > mid) {
|
|
ans += query(c.right, mid + 1, r, s, e);
|
|
}
|
|
return ans;
|
|
}
|
|
|
|
}
|
|
|
|
public static class Right {
|
|
public int[] arr;
|
|
|
|
public Right(int size) {
|
|
arr = new int[size + 1];
|
|
}
|
|
|
|
public void add(int s, int e, int v) {
|
|
for (int i = s; i <= e; i++) {
|
|
arr[i] += v;
|
|
}
|
|
}
|
|
|
|
public void update(int s, int e, int v) {
|
|
for (int i = s; i <= e; i++) {
|
|
arr[i] = v;
|
|
}
|
|
}
|
|
|
|
public int query(int s, int e) {
|
|
int sum = 0;
|
|
for (int i = s; i <= e; i++) {
|
|
sum += arr[i];
|
|
}
|
|
return sum;
|
|
}
|
|
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int n = 1000;
|
|
int value = 50;
|
|
int createTimes = 5000;
|
|
int operateTimes = 5000;
|
|
System.out.println("测试开始");
|
|
for (int i = 0; i < createTimes; i++) {
|
|
int size = (int) (Math.random() * n) + 1;
|
|
DynamicSegmentTree dst = new DynamicSegmentTree(size);
|
|
Right right = new Right(size);
|
|
for (int k = 0; k < operateTimes; k++) {
|
|
double choose = Math.random();
|
|
if (choose < 0.333) {
|
|
int a = (int) (Math.random() * size) + 1;
|
|
int b = (int) (Math.random() * size) + 1;
|
|
int s = Math.min(a, b);
|
|
int e = Math.max(a, b);
|
|
int v = (int) (Math.random() * value);
|
|
dst.update(s, e, v);
|
|
right.update(s, e, v);
|
|
} else if (choose < 0.666) {
|
|
int a = (int) (Math.random() * size) + 1;
|
|
int b = (int) (Math.random() * size) + 1;
|
|
int s = Math.min(a, b);
|
|
int e = Math.max(a, b);
|
|
int v = (int) (Math.random() * value);
|
|
dst.add(s, e, v);
|
|
right.add(s, e, v);
|
|
} else {
|
|
int a = (int) (Math.random() * size) + 1;
|
|
int b = (int) (Math.random() * size) + 1;
|
|
int s = Math.min(a, b);
|
|
int e = Math.max(a, b);
|
|
int ans1 = dst.query(s, e);
|
|
int ans2 = right.query(s, e);
|
|
if (ans1 != ans2) {
|
|
System.out.println("出错了!");
|
|
System.out.println(ans1);
|
|
System.out.println(ans2);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
System.out.println("测试结束");
|
|
}
|
|
|
|
}
|