这两份封装线段树(本题树剖需要用到)有什么区别
//1
namespace segment_tree{
// int new_val[400001*3],lazy[400001*3];
// int tree[400001*3];
int tree[400001*3],lazy[400001*3];
int new_val[400001*3];
il void pushdown(int root,int len) {
lazy[root<<1]+=lazy[root];
lazy[root<<1|1]+=lazy[root];
tree[root<<1]+=lazy[root]*(len-(len>>1));
tree[root<<1|1]+=lazy[root]*(len>>1);
lazy[root]=0;
}
il void upd(int root,int l,int r,int L,int R,int k) {
if (L<=l and r<=R) {
lazy[root]+=k;
tree[root]+=k*(r-l+1);
} else {
if (lazy[root]) pushdown(root,(r-l+1));
if (L<=((l+r)>>1)) upd(root<<1,l,(l+r)>>1,L,R,k);
if (R>((l+r)>>1)) upd(root<<1|1,((l+r)>>1)+1,r,L,R,k);
tree[root]=tree[root<<1]+tree[root<<1|1];
}
}
il void ask(int root,int l,int r,int L,int R) {
if (L<=l and r<=R) {
res+=tree[root];
return;
} else {
if (lazy[root]) pushdown(root,(r-l+1));
if (L<=((l+r)>>1)) ask(root<<1,l,(l+r)>>1,L,R);
if (R>((l+r)>>1)) ask(root<<1|1,((l+r)>>1)+1,r,L,R);
}
}
}
using namespace segment_tree;
//2
namespace segment_tree{
int new_val[400001*3],lazy[400001*3];
int tree[400001*3];
// int tree[400001*3],lazy[400001*3];
// int new_val[400001*3];
il void pushdown(int root,int len) {
lazy[root<<1]+=lazy[root];
lazy[root<<1|1]+=lazy[root];
tree[root<<1]+=lazy[root]*(len-(len>>1));
tree[root<<1|1]+=lazy[root]*(len>>1);
lazy[root]=0;
}
il void upd(int root,int l,int r,int L,int R,int k) {
if (L<=l and r<=R) {
lazy[root]+=k;
tree[root]+=k*(r-l+1);
} else {
if (lazy[root]) pushdown(root,(r-l+1));
if (L<=((l+r)>>1)) upd(root<<1,l,(l+r)>>1,L,R,k);
if (R>((l+r)>>1)) upd(root<<1|1,((l+r)>>1)+1,r,L,R,k);
tree[root]=tree[root<<1]+tree[root<<1|1];
}
}
il void ask(int root,int l,int r,int L,int R) {
if (L<=l and r<=R) {
res+=tree[root];
return;
} else {
if (lazy[root]) pushdown(root,(r-l+1));
if (L<=((l+r)>>1)) ask(root<<1,l,(l+r)>>1,L,R);
if (R>((l+r)>>1)) ask(root<<1|1,((l+r)>>1)+1,r,L,R);
}
}
}
using namespace segment_tree;