前缀和，线段树，树状数组，ST表四种数据结构的辨析

前缀和主要用于解决区间求和，线段数组主要用于动态的区间统计，ST表主要用于查询区间最值，线段树主要用于查询动态的区间最值

主要公式:

pre[i] = pre[i-1] + g[i]; pre[i][j] = g[i][j] - pre[i-1][j-1] + pre[i-1][j] + pre[i][j-1]; S = pre[x2][y2] + pre[x1-1][y1-1] - pre[x1-1][y2] - pre[x2][y1-1];

树状数组主要公式：单体添加，动态范围查询

static int lowbit(int x){ return x & -x; } static void add(int x,int v){ while(x<=n){ tree[x] += v; x += lowbit(x); } } static int sum(int x){ int res = 0; while(x>0){ res += tree[x]; x -= lowbit(x); } return res; }

注：一般范围查询就用sum(r) - sum(l-1);

ST表：主要用于静态范围查询最值,举个模版题

import java.util.*; import java.io.*; public class Main{ static int n; static int [] a; static int [][] st; static int [] log; public static void main(String[] args)throws Exception{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stt = new StringTokenizer(bf.readLine()); n = Integer.parseInt(stt.nextToken()); int m = Integer.parseInt(stt.nextToken()); a = new int [n+1]; st = new int [n+1][20]; log = new int[n+1]; stt = new StringTokenizer(bf.readLine()); for(int i=1;i<=n;i++){ a[i] = Integer.parseInt(stt.nextToken()); st[i][0] = a[i]; } for(int i=2;i<=n;i++){ log[i] = log[i>>1] + 1; } for(int j=1;j<=log[n];j++){ for(int i=1;i+(1<<j)-1<=n;i++){ st[i][j] = Math.max(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } StringBuilder sb = new StringBuilder(); while(m-->0){ stt = new StringTokenizer(bf.readLine()); int L = Integer.parseInt(stt.nextToken()); int R = Integer.parseInt(stt.nextToken()); int k = log[R-L+1]; int ans = Math.max(st[L][k],st[R-(1<<k)+1][k]); sb.append(ans).append("\n"); } System.out.print(sb.toString()); } }

注意两个地方：一个就是固定公式st[i][j] = Math.max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

int ans = Math.max(st[L][k],st[R-(1<<k)+1][k]);

还有就是这题求的是最大值，如果要求最小值的话，把两个max换成min就可以了

离散化：数据很大又很乱时，但是你只关心数据的大小关系，而算法只需要下标时就可以用，举个例子：

import java.io.*; import java.util.*; public class Main { static int n; static int[] h; // 身高（离散化后是排名） static int[] tree; // 树状数组 // lowbit static int lowbit(int x) { return x & -x; } // 树状数组：单点加 1 static void add(int x, int v) { while (x <= n) { tree[x] += v; x += lowbit(x); } } // 树状数组：前缀和 static int sum(int x) { int res = 0; while (x > 0) { res += tree[x]; x -= lowbit(x); } return res; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); h = new int[n]; for (int i = 0; i < n; i++) { h[i] = Integer.parseInt(br.readLine()); } // ====================== //离散化 // ====================== int[] b = h.clone(); Arrays.sort(b); // 去重 int m = 0; for (int i = 0; i < n; i++) { if (i == 0 || b[i] != b[i - 1]) { b[m++] = b[i]; } } // 映射为排名（1-based） for (int i = 0; i < n; i++) { h[i] = Arrays.binarySearch(b, 0, m, h[i]) + 1; } // ====================== //树状数组统计逆序对 // ====================== tree = new int[n + 1]; long ans = 0; for (int i = 0; i < n; i++) { int x = h[i]; // 左边比它大的数量 ans += i - sum(x); // 当前元素加入 add(x, 1); } System.out.println(ans); } }