线段树
不含懒标记(单点修改)
代码
维护区间最大/最小值
Node[] tr = new Node[400010];
class Node{
int l, r, max, min;
Node(int l, int r, int max, int min){
this.l = l;
this.r = r;
this.max = max;
this.min = min;
}
}
void build(int u, int l, int r){
tr[u] = new Node(l, r, 0, 0x3f3f3f3f);
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void pushup(int u){
tr[u].max = Math.max(tr[u << 1].max, tr[u << 1 | 1].max);
tr[u].min = Math.min(tr[u << 1].min, tr[u << 1 | 1].min);
}
int query1(int u, int l, int r){
if(l <= tr[u].l && tr[u].r <= r) return tr[u].max;
int mid = tr[u].l + tr[u].r >> 1, v = 0;
if(l <= mid) v = query1(u << 1, l, r);
if(r > mid) v = Math.max(v, query1(u << 1 | 1, l, r));
return v;
}
int query2(int u, int l, int r){
if(l <= tr[u].l && tr[u].r <= r) return tr[u].min;
int mid = tr[u].l + tr[u].r >> 1, v = 0x3f3f3f3f;
if(l <= mid) v = query2(u << 1, l, r);
if(r > mid) v = Math.min(v, query2(u << 1 | 1, l, r));
return v;
}
void update(int u, int x, int v){
if(tr[u].l == x && tr[u].r == x) {
tr[u].max = v;
tr[u].min = v;
}
else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) update(u << 1, x, v);
else update(u << 1 | 1, x, v);
pushup(u);
}
}
含懒标记(区间修改)
代码
static Node[] tr = new Node[4 * N];
static class Node {
int l, r;
long sum, add;
public Node(int l, int r, long sum, long add) {
this.l = l;
this.r = r;
this.sum = sum;
this.add = add;
}
}
static void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
static void pushdown(int u){
Node root = tr[u], left = tr[u << 1], right = tr[u << 1 | 1];
if(root.add != 0){
left.add += root.add;
left.sum += (left.r - left.l + 1) * root.add;
right.add += root.add;
right.sum += (right.r - right.l + 1) * root.add;
root.add = 0;
}
}
static void build(int u, int l, int r){
if(l == r) tr[u] = new Node(l, r, w[l], 0);
else{
tr[u] = new Node(l, r, 0, 0);
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
static void modify(int u, int l, int r, int d){
if(tr[u].l >= l && tr[u].r <= r) {
tr[u].add += d;
tr[u].sum += (long) (tr[u].r - tr[u].l + 1) * d;
}else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, d);
if(r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
static long query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
long res = 0;
if(l <= mid) res = query(u << 1, l, r);
if(r > mid) res += query(u << 1 | 1, l, r);
return res;
}
}
标签:Node,Java,min,int,线段,tr,mid,sum
From: https://www.cnblogs.com/tobuv/p/17527329.html