树状数组
参考理解链接：https://www.acwing.com/file_system/file/content/whole/index/content/551838/
int lowbit(int x)
{
return x&-x;
}
int ask(int k) //区间查询
{
int res=0;
for(int i=k;i;i-=lowbit(i))
res+=c[i];
return res;
}
void add(int k,int num) // 单点修改
{
for(int i=k;i<=n;i+=lowbit(i))
c[i]+=num;
}可以用前缀和差分的思想改为区间修改和单点查询
线段树
1. 简单版本 （无pushdown，懒标记）
区间查询，单点修改。属性：区间最大值
struct Node
{
int l, r;
int v;
}tr[N*4];
void build(int u, int l, int r)
{
tr[u]={l, r};
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].v=max(tr[u<<1].v, tr[u<<1|1].v);
}
void modify(int u, int k, int t)
{
if(tr[u].l==k && tr[u].r==k)
{
tr[u].v=t;
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(k<=mid) modify(u<<1, k, t);
else modify(u<<1|1, k, t);
pushup(u);
}
int query(int u, int l, int r)
{
if(tr[u].l>=l && tr[u].r<=r) return tr[u].v;
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid) res=query(u<<1, l, r);
if(r>mid) res=max(res, query(u<<1|1, l, r));
return res;
}