线段树基本操作

int query(int u, int l, int r) { //查询操作
  if (tr[u].l >= l && tr[u].r <= r)return tr[u].v; //树中节点已经被完全包含在[l,r]中
  int mid = tr[u].l + tr[u].r >> 1;
  int v = 0;
  if(l > mid)return query(u << 1 | 1,l,r);
    else if(r <= mid)return query(u << 1,l,r);
    else{
        int a = query(u << 1,l,r);
        int b = query(u << 1 | 1, l, r);
        return max(a,b);
    }
  return v;
}

void build(int u, int l, int r) { //建树
  tr[u].l = l, tr[u].r = r; 
  if (l == r)return;
  int mid = l + r >> 1;
  build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int x, int v) { //u表示当前线段树区间 x表示待修改的位置 v表示修改的值
  if (tr[u].l == x && tr[u].r == x)tr[u].v = v;
  else {
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid)modify(u << 1, x, v);
    else modify(u << 1 | 1, x, v);
    pushup(u);
  }
}

void pushup(Node& u, Node& l, Node& r) {
  u.sum = l.sum + r.sum;
  u.d = gcd(l.d, r.d);
}
void pushup(int u) {
  pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(int u) {
  node& root = tr[u];
  node& left = tr[u << 1];
  node& right = tr[u << 1 | 1];
  if (root.add) {
    left.sum += (LL)(left.r - left.l + 1) * root.add;
    right.sum += (LL)(right.r - right.l + 1) * root.add;
    left.add += root.add;
    right.add += root.add;
    root.add = 0;
  }
}