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

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;
    }
    //区间修改:给区间每个值加d
    public 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));
            }
        }
    }
}