对于OI中树的分类
前言
让我们学习 OI，保护生物多样性！
现在 OI 中创造发现了大量形态各异，习性不同的树，对此我们要对它们进行分类（要不然作者写这个干什么），我们决定使用生物分类法分类这些生物。
明确几点：
1.本文将整理 OI wiki 中所有的 计算机科学界——OI门——数据结构纲——树形结构目 以下的生物
开干
线段树科
线段树是算法竞赛中常用的用来维护 区间信息 的生物。
线段树可以在
普通线段树种
普通线段树可以支持区间修改及询问，是线段树科中最简单的生物。
其使用 lazy_tag，可以显著降低它的时间复杂度。
typedef long long LL;
LL n, a[100005], d[270000], b[270000];
void build(LL l, LL r, LL p) { // l:区间左端点 r:区间右端点 p:节点标号
if (l == r) {
d[p] = a[l]; // 将节点赋值
return;
}
LL m = l + ((r - l) >> 1);
build(l, m, p << 1), build(m + 1, r, (p << 1) | 1); // 分别建立子树
d[p] = d[p << 1] + d[(p << 1) | 1];
}
void update(LL l, LL r, LL c, LL s, LL t, LL p) {
if (l <= s && t <= r) {
d[p] += (t - s + 1) * c, b[p] += c; // 如果区间被包含了，直接得出答案
return;
}
LL m = s + ((t - s) >> 1);
if (b[p])
d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
b[p] = 0;
if (l <= m)
update(l, r, c, s, m, p << 1); // 本行和下面的一行用来更新p*2和p*2+1的节点
if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
d[p] = d[p << 1] + d[(p << 1) | 1]; // 计算该节点区间和
}
LL getsum(LL l, LL r, LL s, LL t, LL p) {
if (l <= s && t <= r) return d[p];
LL m = s + ((t - s) >> 1);
if (b[p])
d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
b[p] = 0;
LL sum = 0;
if (l <= m)
sum =
getsum(l, r, s, m, p << 1); // 本行和下面的一行用来更新p*2和p*2+1的答案
if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
return sum;
}
猫树种
所谓「猫树」就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。
构造一棵这样的静态线段树需要
在处理线性基这样特殊的信息的时候甚至可以将复杂度降至
这是Judge_Cheung的分析成果，感谢大佬（我写的随缘补）
namespace cat_tree{
int len,lg[M<<1],pos[M];
int p[16][M],s[16][M],f[16][M],g[16][M];
#define ls k<<1
#define rs k<<1|1
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
inline int Max(int a,int b){return a>b?a:b;}
inline void init(){
for(len=2;len<n;len<<=1);
int l=len<<1;
for(int i=1;i<=l;++i)
lg[i]=lg[i>>1]+1;
}
void build(int k,int l,int r,int d){
if(l==r) return pos[l]=k,void();
int prep,sm;
f[d][mid]=g[d][mid]=a[mid];
p[d][mid]=s[d][mid]=a[mid];
prep=sm=a[mid],sm=Max(sm,0);
for(int i=mid-1;i>=l;--i){
prep+=a[i],sm+=a[i],s[d][i]=prep,
f[d][i]=Max(f[d][i+1],prep),g[d][i]=sm,
p[d][i]=Max(p[d][i+1],sm),sm=Max(sm,0);
}
f[d][mid+1]=g[d][mid+1]=a[mid+1];
p[d][mid+1]=s[d][mid+1]=a[mid+1];
prep=sm=a[mid+1],sm=Max(sm,0);
for(int i=mid+2;i<=r;++i){
prep+=a[i],sm+=a[i],s[d][i]=prep,
f[d][i]=Max(f[d][i-1],prep),g[d][i]=sm,
p[d][i]=Max(p[d][i-1],sm),sm=Max(sm,0);
}
build(lson,d+1),build(rson,d+1);
}
inline int query_sum(int l,int r){
if(l>r) return 0;
if(l==r) return a[l];
int d=lg[pos[l]]-lg[pos[l]^pos[r]];
return s[d][l]+s[d][r];
}
inline int query_pre(int l,int r){
if(l>r) return 0;
if(l==r) return a[l];
int d=lg[pos[l]]-lg[pos[l]^pos[r]];
return Max(s[d][l]+f[d][r],g[d][l]);
}
inline int query_suf(int l,int r){
if(l>r) return 0;
if(l==r) return a[l];
int d=lg[pos[l]]-lg[pos[l]^pos[r]];
return Max(g[d][r],f[d][l]+s[d][r]);
}
inline int query_mid(int l,int r){
if(l>r) return 0;
if(l==r) return a[l];
int d=lg[pos[l]]-lg[pos[l]^pos[r]];
return Max(Max(p[d][l],p[d][r]),f[d][l]+f[d][r]);
}
} using namespace cat_tree;
inline int query(int l1,int r1,int l2,int r2){
int ans;
if(r1<l2) return query_sum(r1+1,l2-1)+query_suf(l1,r1)+query_pre(l2,r2);
ans=query_mid(l2,r1);
if(l1<l2) ans=Max(ans,query_suf(l1,l2)+query_pre(l2,r2)-a[l2]);
if(r2>r1) ans=Max(ans,query_suf(l1,r1)+query_pre(r1,r2)-a[r1]);
return ans;
}权值线段树种
权值线段树种是把区间信息保留在树上的特殊线段树，最早是普通线段树种的一支，后从变种线段树上升到种的层次，快速抢占生态位。
int tr[N*4];
inline void pushup(int x){
tr[x]=tr[x*2]+tr[x*2+1];
}
void insert(int x,int l,int r,int k){
//插入一个数k
if(l==r){
tr[x]++;
return;
}
int mid=(l+r)/2;
if(k<=mid) insert(x*2,l,mid,k);
else insert(x*2+1,mid+1,r,k);
pushup(x);
}
void del(int x,int l,int r,int k){
//删除一个数k
if(l==r){
tr[x]--;
return;
}
int mid=(l+r)/2;
if(k<=mid) del(x*2,l,mid,k);
else del(x*2+1,mid+1,r,k);
pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
//查询ql，qr之间一共有多少个数
if(l>=ql&&r<=qr) return tr[x];
int mid=(l+r)/2,sum=0;
if(ql<=mid) sum=query(x*2,l,mid,ql,qr);
if(qr>mid) sum+=query(x*2+1,mid+1,r,ql,qr);
return sum;
}