树结点结构体
#define lc p << 1
#define rc p << 1 | 1
const int N = 500000
int w[N];//目标数组
struct node {
int l,int r,int sum;
}tr[4 * N];
建树
void bulid(int p,int l,int r) {
tr[p] = {l,r,w[l]};
if(l == r) return;
int mid = l + r >> 1;
bulit(lc,l,mid);
built(rc,mid + 1,r);
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
单点修改
void update(int p,int index,int val) {
if(tr[p].l == index && tr[p].r == index) {
tr[p],sum == val;
return;
}
int mid = tr[p].l + tr[p].r >> 1;
if(index <= mid) update(lc,index,val);
if(index > mid) update(rc,index,val);
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
区间查询
int query(int p,int l,int r) {
if(l <= tr[p].l && r >= tr[p].r) {
return tr[p].sum;
}
int mid = tr[p].l + tr[p].r >> 1;
int sum = 0;
if(l <= mid) sum += query(lc,l,r);
if(r > mid) sum += query(rc,l,r);
return sum;
}
区间修改(加上懒标记)
#define lc p << 1
#define rc p << 1 | 1
#define N 500000
struct node {
int l,r,sum,add;
}tr[4 * N];
void pushup(int p) {
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(int p) {
if(tr[p].add) {
tr[lc].sum = tr[p].add * (tr[lc].r - tr[lc].l + 1);
tr[rc].sum = tr[p].add * (tr[rc].r - tr[rc].l + 1);
tr[lc].add += tr[p].add;
tr[rc].add += tr[p].add;
tr[p].add = 0;
}
}
void update(int p,int l,int r,int val) {
if(l <= tr[p].l && r >= tr[p].r) {
tr[p].sum += (tr[p].r - tr[p].l + 1) * val;
tr[p].add += k;
return;
}
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
if(l <= mid) update(lc,l,r,val);
if(r > mid) update(rc,l,r,val);
pushup(p);
}