线段树
占位先,作为一个线段树都能写炸的蒟蒻一定要些点东西
没错我来写这个线段树的笔记了
# lofter支持markdown 吗?
lofter上好像不支持md,那就没有更丰富的展现了(?)
线段树能区间修改,区间求最小值
对于单点修改,区间求和的出门左转“树状数组”(树状数组那么好写谁还写线段树)
代码
#define MAX 50010
#define lson (id<<1) //id*2
#define rson (id<<1|1)
int tree[MAX * 4], a[MAX];
inline void build(int l, int r, int id){
if(l == r){
tree[id]= a[l];
return;
}
else{
int mid =(l + r)/2;
build(l, mid, lson);
build(mid + 1, r, rson);
tree[id]= min(tree[lson], tree[rson]);
}
}
inline int qnery(int l, int r, int id, int ql, int qr){
if(ql <= l && qr <= qr){
return tree[id];
}
int mid =(l + r) / 2;
int res = 0x3f3f3f3f;
if(mid >= ql){
res = qnery(l, mid, lson, ql, qr);
}
if(mid <= qr){
res = min(res, qnery(mid + 1, r, rson, ql, qr));
}
return res;
}
评论(1)