蓝桥杯备赛第四篇（高级数据结构）

本文主要是介绍蓝桥杯备赛第四篇（高级数据结构），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.树状数组

	public static int getSum(int i) {int sum = 0;for (int j = i; j >= 1; j -= lowbit(j)) {sum += tree[j];}return sum;}public static void update(int i, int update) {for (int j = i; j <= n; j += lowbit(j)) {tree[j] += update;}}public static int lowbit(int num) {return num & -num;}

2.ST表

作用是：快速进行区间查询，ST表创建O ( n l o g ( n ) ) O(nlog(n))O(nlog(n)),查询O ( 1 ) O(1)O(1),不支持在线修改

public class ST表 {static int[] arr;static int n;static int[][] dp;//nlog(n)public static void createST() {int max = (int) (Math.log(n) / Math.log(2));dp = new int[n + 1][max + 1];//自己到自己的最值就是自己for (int i = 1; i < n; i++) {dp[i][0] = arr[i];}for (int j = 1; j <= max; j++) {for (int i = 1; i + (1 << j) - 1 <= n; i++) {dp[i][j] = Math.max(dp[i][j - 1], dp[i + (1 << (j - 1)) + 1][j - 1]);}}}//o(1)public static int query(int l, int r) {int max = (int) (Math.log(l - r + 1) / Math.log(2));return Math.max(dp[l][max], dp[r - (1 << max) + 1][max]);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();arr = new int[n + 1];for (int i = 1; i <= n; i++) {arr[i] = scanner.nextInt();}}
}

3.线段树

//区间和
import java.util.Scanner;
public class Main {static int[] a;static int n;static Node[] tree;static class Node {int l;int r;int num;int lazy;//用于记录对于这个节点进行过什么操作public Node(int l, int r, int num) {this.l = l;this.r = r;this.num = num;}}public static void build(int index, int l, int r) {if (l == r) {tree[index] = new Node(l, r, a[l]);return;}int mid = (l + r) / 2;build(index * 2, l, mid);build(index * 2 + 1, mid + 1, r);tree[index] = new Node(l, r, tree[index * 2].num + tree[index * 2 + 1].num);}//单点修改public static void update(int index, int i, int newnum) {if (tree[index].l == tree[index].r && tree[index].r == i) {tree[index].num = newnum;return;}int mid = (tree[index].l + tree[index].r) / 2;if (i <= mid) {update(index * 2, i, newnum);} else {update(index * 2 + 1, i, newnum);}tree[index].num = tree[index * 2].num + tree[index * 2 + 1].num;}//区间修改:给区间每个值加dpublic static void change(int index, int l, int r, int d) {if (l <= tree[index].l && tree[index].r <= r) {tree[index].num += (tree[index].r - tree[index].l + 1) * d;tree[index].lazy += d;return;}spred(index);int mid = (tree[index].l + tree[index].r) / 2;if (l <= mid) {change(index * 2, l, r, d);}if (r > mid) {change(index * 2 + 1, l, r, d);}tree[index].num = tree[index * 2].num + tree[index * 2 + 1].num;}//一共5个步骤public static void spred(int index) {if (tree[index].lazy != 0) {tree[index * 2].num += (tree[index * 2].r - tree[index * 2].l + 1) * tree[index].lazy;tree[index * 2 + 1].num += (tree[index * 2 + 1].r - tree[index * 2 + 1].l + 1) * tree[index].lazy;tree[index * 2].lazy += tree[index].lazy;tree[index * 2 + 1].lazy += tree[index].lazy;tree[index].lazy = 0;}}public static int ask(int index, int l, int r) {if (l <= tree[index].l && tree[index].r <= r) {return tree[index].num;}spred(index);int sum = 0;int mid = (tree[index].l + tree[index].r) / 2;if (l <= mid) {sum += ask(index * 2, l, r);}if (r > mid) {sum += ask(index * 2 + 1, l, r);}return sum;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();a = new int[n + 1];tree = new Node[n * 4];int m = scanner.nextInt();for (int i = 1; i <= n; i++) {a[i] = scanner.nextInt();}build(1, 1, n);for (int i = 0; i < m; i++) {int caozuo = scanner.nextInt();if (caozuo == 1) {int x = scanner.nextInt();int y = scanner.nextInt();int k = scanner.nextInt();change(1, x, y, k);} else {int x = scanner.nextInt();int y = scanner.nextInt();System.out.println(ask(1, x, y));}}}
}