线段树的原理

1.如果知道两个子范围上的最值，通过比较就可以知道整个范围上的最值

2.如果知道两个子范围上分别出现的次数最多的数，但无法知道整个范围上出现最多的数

范围修改logn的前提：如果维护的是区域和，要把区域上的每个数字加上a，只需要知道区域中数字的个数乘以a加到原数字和上就可以得到新的和，时间复杂度为O(1)，那么这样的修改复杂度就是logn；如果是将区域上的每个数数位上的数字都倒置得到新的数字，那么这样是无法直接得到新的累加和的，这样的修改操作就不是logn

 

 

  P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

范围查询，范围修改

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {public static int MAXN = 100001;public static long[] arr = new long[MAXN];public static long[] sum = new long[MAXN << 2];public static long[] add = new long[MAXN << 2];// 累加和信息的汇总public static void up(int i) {// 父范围的累加和 = 左范围累加和 + 右范围累加和sum[i] = sum[i << 1] + sum[i << 1 | 1];}// 懒信息的下发public static void down(int i, int ln, int rn) {if (add[i] != 0) {// 发左lazy(i << 1, add[i], ln);// 发右lazy(i << 1 | 1, add[i], rn);// 父范围懒信息清空add[i] = 0;}}// 当前来到l~r范围，对应的信息下标是i，范围上数字的个数是n = r-l+1// 现在收到一个懒更新任务 : l~r范围上每个数字增加v// 这个懒更新任务有可能是任务范围把当前线段树范围全覆盖导致的// 也有可能是父范围的懒信息下发下来的// 总之把线段树当前范围的sum数组和add数组调整好// 就不再继续往下下发了，懒住了public static void lazy(int i, long v, int n) {sum[i] += v * n;add[i] += v;}// 建树public static void build(int l, int r, int i) {if (l == r) {sum[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}add[i] = 0;}// 范围修改// jobl ~ jobr范围上每个数字增加jobvpublic static void add(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv, r - l + 1);} else {int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);if (jobl <= mid) {add(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}// 查询累加和public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);long ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken(); int n = (int) in.nval;in.nextToken(); int m = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();arr[i] = (long) in.nval;}build(1, n, 1);long jobv;for (int i = 1, op, jobl, jobr; i <= m; i++) {in.nextToken();op = (int) in.nval;if (op == 1) {in.nextToken(); jobl = (int) in.nval;in.nextToken(); jobr = (int) in.nval;in.nextToken(); jobv = (long) in.nval;add(jobl, jobr, jobv, 1, n, 1);} else {in.nextToken(); jobl = (int) in.nval;in.nextToken(); jobr = (int) in.nval;out.println(query(jobl, jobr, 1, n, 1));}}out.flush();out.close();br.close();}}

范围查询，单点修改

public class Code02_SegmentTreeUpdateQuerySum {public static int MAXN = 100001;public static long[] arr = new long[MAXN];public static long[] sum = new long[MAXN << 2];public static long[] change = new long[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static void up(int i) {sum[i] = sum[i << 1] + sum[i << 1 | 1];}public static void down(int i, int ln, int rn) {if (update[i]) {lazy(i << 1, change[i], ln);lazy(i << 1 | 1, change[i], rn);update[i] = false;}}public static void lazy(int i, long v, int n) {sum[i] = v * n;change[i] = v;update[i] = true;}public static void build(int l, int r, int i) {if (l == r) {sum[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}change[i] = 0;update[i] = false;}public static void update(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv, r - l + 1);} else {int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);long ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}// 对数器逻辑// 展示了线段树的建立和使用// 使用验证结构来检查线段树是否正常工作public static void main(String[] args) {System.out.println("测试开始");int n = 1000;int v = 2000;int t = 5000000;// 生成随机值填入arr数组randomArray(n, v);// 建立线段树build(1, n, 1);// 生成验证的结构long[] check = new long[n + 1];for (int i = 1; i <= n; i++) {check[i] = arr[i];}for (int i = 1; i <= t; i++) {// 生成操作类型// op = 0 更新操作// op = 1 查询操作int op = (int) (Math.random() * 2);// 下标从1开始，不从0开始，生成两个随机下标int a = (int) (Math.random() * n) + 1;int b = (int) (Math.random() * n) + 1;// 确保jobl <= jobrint jobl = Math.min(a, b);int jobr = Math.max(a, b);if (op == 0) {// 更新操作// 线段树、验证结构同步更新int jobv = (int) (Math.random() * v * 2) - v;update(jobl, jobr, jobv, 1, n, 1);checkUpdate(check, jobl, jobr, jobv);} else {// 查询操作// 线段树、验证结构同步查询// 比对答案long ans1 = query(jobl, jobr, 1, n, 1);long ans2 = checkQuery(check, jobl, jobr);if (ans1 != ans2) {System.out.println("出错了!");}}}System.out.println("测试结束");}

 

 

public class Code03_SegmentTreeAddQueryMax {public static int MAXN = 100001;public static long[] arr = new long[MAXN];public static long[] max = new long[MAXN << 2];public static long[] add = new long[MAXN << 2];public static void up(int i) {max[i] = Math.max(max[i << 1], max[i << 1 | 1]);}public static void down(int i) {if (add[i] != 0) {lazy(i << 1, add[i]);lazy(i << 1 | 1, add[i]);add[i] = 0;}}public static void lazy(int i, long v) {max[i] += v;add[i] += v;}public static void build(int l, int r, int i) {if (l == r) {max[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}add[i] = 0;}public static void add(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv);} else {down(i);int mid = (l + r) >> 1;if (jobl <= mid) {add(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return max[i];}down(i);int mid = (l + r) >> 1;long ans = Long.MIN_VALUE;if (jobl <= mid) {ans = Math.max(ans, query(jobl, jobr, l, mid, i << 1));}if (jobr > mid) {ans = Math.max(ans, query(jobl, jobr, mid + 1, r, i << 1 | 1));}return ans;}// 对数器逻辑// 展示了线段树的建立和使用// 使用验证结构来检查线段树是否正常工作public static void main(String[] args) {System.out.println("测试开始");int n = 1000;int v = 2000;int t = 5000000;// 生成随机值填入arr数组randomArray(n, v);// 建立线段树build(1, n, 1);// 生成验证的结构long[] check = new long[n + 1];for (int i = 1; i <= n; i++) {check[i] = arr[i];}for (int i = 1; i <= t; i++) {// 生成操作类型// op = 0 增加操作// op = 1 查询操作int op = (int) (Math.random() * 2);// 下标从1开始，不从0开始，生成两个随机下标int a = (int) (Math.random() * n) + 1;int b = (int) (Math.random() * n) + 1;// 确保jobl <= jobrint jobl = Math.min(a, b);int jobr = Math.max(a, b);if (op == 0) {// 增加操作// 线段树、验证结构同步增加int jobv = (int) (Math.random() * v * 2) - v;add(jobl, jobr, jobv, 1, n, 1);checkAdd(check, jobl, jobr, jobv);} else {// 查询操作// 线段树、验证结构同步查询// 比对答案long ans1 = query(jobl, jobr, 1, n, 1);long ans2 = checkQuery(check, jobl, jobr);if (ans1 != ans2) {System.out.println("出错了!");}}}System.out.println("测试结束");}

 

public class Code04_SegmentTreeUpdateQueryMax {public static int MAXN = 100001;public static long[] arr = new long[MAXN];public static long[] max = new long[MAXN << 2];public static long[] change = new long[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static void up(int i) {max[i] = Math.max(max[i << 1], max[i << 1 | 1]);}public static void down(int i) {if (update[i]) {lazy(i << 1, change[i]);lazy(i << 1 | 1, change[i]);update[i] = false;}}public static void lazy(int i, long v) {max[i] = v;change[i] = v;update[i] = true;}public static void build(int l, int r, int i) {if (l == r) {max[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}change[i] = 0;update[i] = false;}public static void update(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {lazy(i, jobv);} else {down(i);int mid = (l + r) >> 1;if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return max[i];}down(i);int mid = (l + r) >> 1;long ans = Long.MIN_VALUE;if (jobl <= mid) {ans = Math.max(ans, query(jobl, jobr, l, mid, i << 1));}if (jobr > mid) {ans = Math.max(ans, query(jobl, jobr, mid + 1, r, i << 1 | 1));}return ans;}// 对数器逻辑// 展示了线段树的建立和使用// 使用验证结构来检查线段树是否正常工作public static void main(String[] args) {System.out.println("测试开始");int n = 1000;int v = 2000;int t = 5000000;// 生成随机值填入arr数组randomArray(n, v);// 建立线段树build(1, n, 1);// 生成验证的结构long[] check = new long[n + 1];for (int i = 1; i <= n; i++) {check[i] = arr[i];}for (int i = 1; i <= t; i++) {// 生成操作类型// op = 0 更新操作// op = 1 查询操作int op = (int) (Math.random() * 2);// 下标从1开始，不从0开始，生成两个随机下标int a = (int) (Math.random() * n) + 1;int b = (int) (Math.random() * n) + 1;// 确保jobl <= jobrint jobl = Math.min(a, b);int jobr = Math.max(a, b);if (op == 0) {// 更新操作// 线段树、验证结构同步更新int jobv = (int) (Math.random() * v * 2) - v;update(jobl, jobr, jobv, 1, n, 1);checkUpdate(check, jobl, jobr, jobv);} else {// 查询操作// 线段树、验证结构同步查询// 比对答案long ans1 = query(jobl, jobr, 1, n, 1);long ans2 = checkQuery(check, jobl, jobr);if (ans1 != ans2) {System.out.println("出错了!");}}}System.out.println("测试结束");}

 

 

 

 

 1.lazy：如果来的是add操作，那么就在之前update操作上继续加即可，update操作不需要改变；如果是update操作，那么之前的add操作就相当于没发生过，所以add数组置为0；

2.如果父节点既有add信息又有update信息，我们知道，如果有update操作，就会把add信息取消，所以update信息一定早于add信息，所以先传递update信息，在传递add信息

public class Code05_SegmentTreeUpdateAddQuerySum {public static int MAXN = 1000001;public static long[] arr = new long[MAXN];public static long[] sum = new long[MAXN << 2];public static long[] add = new long[MAXN << 2];public static long[] change = new long[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static void up(int i) {sum[i] = sum[i << 1] + sum[i << 1 | 1];}public static void down(int i, int ln, int rn) {if (update[i]) {updateLazy(i << 1, change[i], ln);updateLazy(i << 1 | 1, change[i], rn);update[i] = false;}if (add[i] != 0) {addLazy(i << 1, add[i], ln);addLazy(i << 1 | 1, add[i], rn);add[i] = 0;}}public static void updateLazy(int i, long v, int n) {sum[i] = v * n;add[i] = 0;change[i] = v;update[i] = true;}public static void addLazy(int i, long v, int n) {sum[i] += v * n;add[i] += v;}public static void build(int l, int r, int i) {if (l == r) {sum[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}add[i] = 0;change[i] = 0;update[i] = false;}public static void update(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {updateLazy(i, jobv, r - l + 1);} else {int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static void add(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {addLazy(i, jobv, r - l + 1);} else {int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);if (jobl <= mid) {add(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return sum[i];}int mid = (l + r) >> 1;down(i, mid - l + 1, r - mid);long ans = 0;if (jobl <= mid) {ans += query(jobl, jobr, l, mid, i << 1);}if (jobr > mid) {ans += query(jobl, jobr, mid + 1, r, i << 1 | 1);}return ans;}public static void main(String[] args) {System.out.println("测试开始");int n = 1000;int v = 2000;int t = 5000000;// 生成随机值填入arr数组randomArray(n, v);// 建立线段树build(1, n, 1);// 生成验证的结构long[] check = new long[n + 1];for (int i = 1; i <= n; i++) {check[i] = arr[i];}for (int i = 1; i <= t; i++) {// 生成操作类型// op = 0 增加操作// op = 1 更新操作// op = 2 查询操作int op = (int) (Math.random() * 3);// 下标从1开始，不从0开始，生成两个随机下标int a = (int) (Math.random() * n) + 1;int b = (int) (Math.random() * n) + 1;// 确保jobl <= jobrint jobl = Math.min(a, b);int jobr = Math.max(a, b);if (op == 0) {// 增加操作// 线段树、验证结构同步增加int jobv = (int) (Math.random() * v * 2) - v;add(jobl, jobr, jobv, 1, n, 1);checkAdd(check, jobl, jobr, jobv);} else if (op == 1) {// 更新操作// 线段树、验证结构同步更新int jobv = (int) (Math.random() * v * 2) - v;update(jobl, jobr, jobv, 1, n, 1);checkUpdate(check, jobl, jobr, jobv);} else {// 查询操作// 线段树、验证结构同步查询// 比对答案long ans1 = query(jobl, jobr, 1, n, 1);long ans2 = checkQuery(check, jobl, jobr);if (ans1 != ans2) {System.out.println("出错了!");}}}System.out.println("测试结束");}

P1253 扶苏的问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {public static int MAXN = 1000001;public static long[] arr = new long[MAXN];public static long[] max = new long[MAXN << 2];public static long[] add = new long[MAXN << 2];public static long[] change = new long[MAXN << 2];public static boolean[] update = new boolean[MAXN << 2];public static void up(int i) {max[i] = Math.max(max[i << 1], max[i << 1 | 1]);}public static void down(int i) {if (update[i]) {updateLazy(i << 1, change[i]);updateLazy(i << 1 | 1, change[i]);update[i] = false;}if (add[i] != 0) {addLazy(i << 1, add[i]);addLazy(i << 1 | 1, add[i]);add[i] = 0;}}public static void updateLazy(int i, long v) {max[i] = v;add[i] = 0;change[i] = v;update[i] = true;}public static void addLazy(int i, long v) {max[i] += v;add[i] += v;}public static void build(int l, int r, int i) {if (l == r) {max[i] = arr[l];} else {int mid = (l + r) >> 1;build(l, mid, i << 1);build(mid + 1, r, i << 1 | 1);up(i);}add[i] = 0;change[i] = 0;update[i] = false;}public static void update(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {updateLazy(i, jobv);} else {int mid = (l + r) >> 1;down(i);if (jobl <= mid) {update(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {update(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static void add(int jobl, int jobr, long jobv, int l, int r, int i) {if (jobl <= l && r <= jobr) {addLazy(i, jobv);} else {int mid = (l + r) >> 1;down(i);if (jobl <= mid) {add(jobl, jobr, jobv, l, mid, i << 1);}if (jobr > mid) {add(jobl, jobr, jobv, mid + 1, r, i << 1 | 1);}up(i);}}public static long query(int jobl, int jobr, int l, int r, int i) {if (jobl <= l && r <= jobr) {return max[i];}int mid = (l + r) >> 1;down(i);long ans = Long.MIN_VALUE;if (jobl <= mid) {ans = Math.max(ans, query(jobl, jobr, l, mid, i << 1));}if (jobr > mid) {ans = Math.max(ans, query(jobl, jobr, mid + 1, r, i << 1 | 1));}return ans;}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));in.nextToken(); int n = (int) in.nval;in.nextToken(); int m = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();arr[i] = (long) in.nval;}build(1, n, 1);long jobv;for (int i = 1, op, jobl, jobr; i <= m; i++) {in.nextToken();op = (int) in.nval;if (op == 1) {in.nextToken(); jobl = (int) in.nval;in.nextToken(); jobr = (int) in.nval;in.nextToken(); jobv = (long) in.nval;update(jobl, jobr, jobv, 1, n, 1);} else if (op == 2) {in.nextToken(); jobl = (int) in.nval;in.nextToken(); jobr = (int) in.nval;in.nextToken(); jobv = (long) in.nval;add(jobl, jobr, jobv, 1, n, 1);} else {in.nextToken(); jobl = (int) in.nval;in.nextToken(); jobr = (int) in.nval;out.println(query(jobl, jobr, 1, n, 1));}}out.flush();out.close();br.close();}}