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));
}
}
}
}