线段树模板

方法

区间查询

// 当前节点是root，root对应的区间是[l,r]，要查[x,y]的和
int Query(int root, int l, int r, int x, int y) {
    if (l == x && r == y) return sum[root];
      // 如果查询区间与已知区间吻合，直接返回这段区间的和.
    Downtag(root, l, r);
    int mid = (l + r) >> 1, suml = 0, sumr = 0;
    if (x <= mid) suml = Query(ll[root], l, mid, x, min(mid, y));
      // 要查的区间的左端点被左儿子区间包含的时候，也就是说要查的区间和左儿子区间有交集
    if (y > mid) sumr = Query(rr[root], mid + 1, r, max(mid + 1, r), y);
      // 要查的区间的右端点被右儿子区间包含的时候，也就是说要查的区间和右儿子区间有交集
    return suml + sumr;
}

区间修改

//当前节点编号，当前节点对应的区间，要修改的区间编号，增加的值
void Update(int &root, int l, int r, int p, int q, int x) 
{
    if (root == 0) root = ++cnt;
    int num = min(r, q) - max(l, p) + 1; // 当前节点对应区间与查询区间的交集的长度
    sum[root] += x * num;
      // 因为上述交集的每一个元素都要加x，共num个元素，所以root的sum要这样加
    if (l == p && r == q) 
    { // 按上文所说，两区间吻合后执行设置标记操作
    tag[root] += x;
    return; // 本函数内不再执行更深的操作，直接回溯
    }
    int mid = (l + r) >> 1;
    if(p<=mid) Update(ll[root], l, mid, p, min(mid, q), x);
    if(q>mid) Update(rr[root], mid + 1, r, max(mid + 1, p), q, x);
      // 这两处if的作用是递归进入时确保两子区间与查询子区间有交集，防止num为负
}

Downtag

inline void Downtag(int root, int l, int r) 
{
    if (ll[root] == 0) ll[root] = ++cnt;
    if (rr[root] == 0) rr[root] = ++cnt;
    tag[ll[root]] += tag[root], tag[rr[root]] += tag[root];
        // 将标记下放到子区间
    int mid = (l + r) >> 1;
    sum[ll[root]] += tag[root] * (mid - l + 1);
        // 左子区间的和的增加，即对应标记的值（要修改的值）乘左子区间长度
    sum[rr[root]] += tag[root] * (r - mid);
        // 右子区间的和的增加，即对应标记的值（要修改的值）乘右子区间长度
    tag[root] = 0; // 当前节点操作完毕，重置标记值
}