线段树
import java.util.Scanner;
public class Main {
static int n, m;
static int[] num;
static Tree[] tree;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
tree = new Tree[4*n];
for (int i = 0; i < 4*n; i++) {
tree[i] = new Tree();
}
build(1, 0, n - 1);
int l, r, d;
String[] s;
m = sc.nextInt();
sc.nextLine();
for (int i = 0; i < m; i++) {
s = sc.nextLine().split(" ");
l = Integer.parseInt(s[0]);
r = Integer.parseInt(s[1]);
if (s.length == 3) {
//增值操作
d = Integer.parseInt(s[2]);
if (l <= r) {
add(1, l, r, d);
}else {
add(1, l, n-1, d);
add(1, 0, r, d);
}
}else {
//求最小值操作
if (l <= r) {
System.out.println(query(1 ,l, r));
}else {
System.out.println(Math.min(query(1, l, n-1), query(1, 0, r)));
}
}
}
}
private static void build(int node, int left, int right) {
// TODO Auto-generated method stub
tree[node].l = left;
tree[node].r = right;
if (left == right){
tree[node].min = num[left];
return;
}
int mid = (left + right) >> 1;
build(node << 1, left, mid);
build(node << 1 | 1, mid + 1, right);//左移一位后,最后一位一定为0
pushup(node);
}
//修改只是进行上调
private static void pushup(int node) {
// TODO Auto-generated method stub
tree[node].min = Math.min(tree[node<<1].min, tree[node<<1|1].min);
}
private static void add(int node, int start, int end, int d) {
// TODO Auto-generated method stub
if (tree[node].l >= start && tree[node].r <= end) {
tree[node].min += d;
tree[node].lazy += d;
return;
}
pushdown(node);
int mid = (tree[node].l + tree[node].r) >> 1;
if (start <= mid) {
add(node << 1, start, end, d);
}
if (end > mid) {
add(node << 1 | 1, start, end, d);
}
pushup(node);
}
//获取值是进行下调
private static void pushdown(int node) {
// TODO Auto-generated method stub
Tree root = tree[node];
Tree left = tree[node<<1];
Tree right = tree[node<<1|1];
left.min += root.lazy;
left.lazy += root.lazy;
right.min += root.lazy;
right.lazy += root.lazy;
root.lazy = 0;
}
private static long query(int node, int start, int end) {
// TODO Auto-generated method stub
if (tree[node].l >= start && tree[node].r <= end){
return tree[node].min;
}
pushdown(node);
int mid = (tree[node].l + tree[node].r) >> 1;
long res = 0x3f3f3f3f;
if (start <= mid) {
res = Math.min(res, query(node << 1, start, end));
}
if (end > mid) {
res = Math.min(res, query(node << 1 | 1, start, end));
}
return res;
}
}
class Tree{
int l, r;
long min, lazy;
}