悬棺求解（写法问题）

struct node {
    int l, r;       // 区间的左右边界
    ll sum;         // 区间和
    int add;        // 区间加值
    int ls, rs;     // 左右孩子节点
} tr[N << 5];

int cnt = 0;

// Pushdown操作：下传懒标记
void pushdown(int c) {
    auto &t = tr[c];
    if (t.add == 0 || t.l == t.r) return;
    int mid = (t.l + t.r) / 2;  // 计算中点
    if (t.add != 0) {  // 如果有懒标记
        if (t.ls == 0) t.ls = ++cnt;
        if (t.rs == 0) t.rs = ++cnt;

        // 下传加值到左右孩子
        tr[t.ls].sum = tr[t.ls].sum + (mid - t.l + 1) * t.add;
        tr[t.rs].sum = tr[t.rs].sum + (t.r - mid) * t.add;
        tr[t.ls].add = tr[t.ls].add + t.add;
        tr[t.rs].add = tr[t.rs].add + t.add;

        t.add = 0;  // 清空懒标记
    }
}

// 更新操作：更新区间 [L, R] 上的值
void update(int &c, int L, int R, int k, int l, int r) {
    if (!c) c = ++cnt;  // 如果当前节点为空，分配一个新节点
    auto &t = tr[c];
    t.l = l;
    t.r = r;  // 设置区间边界

    if (L <= t.l && R >= t.r) {
        t.sum = t.sum + (t.r - t.l + 1) * k;
        t.add = t.add + k;
        return;
    }
    pushdown(c);  // 推动懒标记
    int mid = (t.l + t.r) / 2;
    if (L <= mid) update(t.ls, L, R, k, t.l, mid);  // 更新左子树
    if (R > mid) update(t.rs, L, R, k, mid + 1, t.r);  // 更新右子树
    t.sum = 0;
    if (t.ls) t.sum = t.sum + tr[t.ls].sum;  // 汇总左子树的和
    if (t.rs) t.sum = t.sum + tr[t.rs].sum;  // 汇总右子树的和
}

// 查询操作：查询区间 [L, R] 上的和
ll query(int c, int L, int R) {
    if (!c) return 0;
    auto &t = tr[c];
    if (L <= t.l && t.r <= R) return t.sum;
    pushdown(c);  // 推动懒标记
    int mid = (t.l + t.r) / 2;
    ll res = 0;
    if (L <= mid) res = res + query(t.ls, L, R);  // 查询左子树
    if (R > mid) res = res + query(t.rs, L, R);  // 查询右子树
    return res;
}

void pushdown(int c,int l,int r) {
    auto &t = tr[c];
    if (t.add == 0 || l == r) return;
    int mid = (l + r) / 2;  // 计算中点
    if (t.add != 0) {  // 如果有懒标记
        if (t.ls == 0) t.ls = ++cnt;
        if (t.rs == 0) t.rs = ++cnt;

        // 下传加值到左右孩子
        tr[t.ls].sum = tr[t.ls].sum + (mid - l + 1) * t.add;
        tr[t.rs].sum = tr[t.rs].sum + (r - mid) * t.add;
        tr[t.ls].add = tr[t.ls].add + t.add;
        tr[t.rs].add = tr[t.rs].add + t.add;

        t.add = 0;  // 清空懒标记
    }
}

// 更新操作：更新区间 [L, R] 上的值
void update(int &c, int L, int R, int k, int l, int r) {
    if (!c) c = ++cnt;  // 如果当前节点为空，分配一个新节点
    auto &t = tr[c];


    if (L <= l && R >= r) {
        t.sum = t.sum + (r - l + 1) * k;
        t.add = t.add + k;
        return;
    }
    pushdown(c,l,r);  // 推动懒标记
    int mid = (l + r) / 2;
    if (L <= mid) update(t.ls, L, R, k, l, mid);  // 更新左子树
    if (R > mid) update(t.rs, L, R, k, mid + 1, r);  // 更新右子树
    t.sum = 0;
    if (t.ls) t.sum = t.sum + tr[t.ls].sum;  // 汇总左子树的和
    if (t.rs) t.sum = t.sum + tr[t.rs].sum;  // 汇总右子树的和
}

// 查询操作：查询区间 [L, R] 上的和
ll query(int c, int L, int R,int l,int r) {
    if (!c) return 0;
    auto &t = tr[c];
    if (L <= l && r <= R) return t.sum;
    pushdown(c,l,r);  // 推动懒标记
    int mid = (l + r) / 2;
    ll res = 0;
    if (L <= mid) res = res + query(t.ls, L, R,l,mid);  // 查询左子树
    if (R > mid) res = res + query(t.rs, L, R,mid+1,r);  // 查询右子树
    return res;
}