线段树

理论

组织

线段树的sum数组在组织时，假定其结构为满二叉树来开空间。
若数据范围为\(1-n\)，则二叉树的层高最大为\(\log_{2}{n}+2\)，节点总数为\((n^{\log_{2}{n}+2})-1\),即\(4n-1\)。

对于一个任意的大范围[l,r]，若将它的信息放在数组中索引为i的元素中，则其子节点按左右范围拆分为[l,mid]和[mid+1,r]，其中左范围信息在数组中的索引为2*i，右范围为2*i+1。

查询

时间复杂度为\(\log_{}{n}\)。

更新

支持增减、重置、和范围改变为指定值

单开一个add数组记录每个值的变化，原则是懒更新，即记录每次更新，直到必须将更新作用到原信息上时才根据add数组执行更新。
其核心思路是如果当前范围全部会被更新，则将更新的内容存在当前范围中。

如果题目中存在范围改变为指定值的操作，为了区分当前懒更新中记录的值是变化值还是重置的指定值，需要额外单开一个isCover[4n+5]数组进行标记。

题目

模板

题目链接：码蹄集OJ-线段树

点击展开题目

线段树模板题。已知一个数列，你需要进行下面两种操作：将某区间每一个数加上 kk，求出某区间每一个数的和。

格式

输入格式：

第一行包含两个整数 n,mn,m (5≤n,m≤1055≤n,m≤105),分别表示该数列数字的个数和操作的总个数；
第二行包含 nn 个用空格分隔的整数 (0−1090−109)，其中第 ii 个数字表示数列第 ii 项的初始值；
接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下:
1 x y k：将区间 [x, y] 内每个数加上 k。
2 x y：输出区间 [x, y]内的数的和。
其中：1≤x≤y≤n,0≤k≤1051≤x≤y≤n,0≤k≤105。

输出格式：

输出包含若干行整数，即为所有操作 2 的结果。

样例 1

输入：

复制

输出：

1
2
3

11
8
20

复制

备注

线段树模板

实现

点击展开代码

#include<iostream> 
#define ll long long
using namespace std;

const int MAX = 1e5 + 5;
ll n, m, k, sign, x, y;
bool isFirst = true;
ll sum[4 * MAX], change[4 * MAX];
ll num[MAX];

void build(ll l, ll r, ll idx) {
    if (l == r) {
        sum[idx] = num[l];
        return;
    }

    ll mid = (l + r) / 2;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    sum[idx] = sum[idx << 1] + sum[idx << 1 | 1];
}

void lazyUpdate(ll l, ll r, ll idx) {
    if (change[idx] == 0)return;
    ll mid = (l + r) / 2;

    change[idx << 1] += change[idx];
    sum[idx << 1] += (mid - l + 1) * change[idx];
    change[idx << 1 | 1] += change[idx];
    sum[idx << 1 | 1] += (r - mid ) * change[idx];

    change[idx] = 0;
}

void update(ll targetL, ll targetR, ll l, ll r, ll idx) {
    if (targetL<=l && targetR>=r) {
        change[idx] += k;
        sum[idx] += (r - l + 1) * k;
        return;
    }

    //向下一层执行更新
    lazyUpdate(l, r, idx);
    ll mid = (l + r) / 2;
    if (targetL <= mid)update(targetL, targetR, l, mid, idx << 1);
    if (targetR > mid)update(targetL, targetR, mid + 1, r, idx << 1 | 1);
    sum[idx] = sum[idx << 1] + sum[idx << 1 | 1];
}

long long res(ll targetL, ll targetR, ll l, ll r, ll idx) {
    if (targetL <= l && r <= targetR)return sum[idx];
    else {
        lazyUpdate(l, r, idx);
        long long ans = 0;
        ll mid = (l + r) / 2;
        if (targetL <= mid)ans += res(targetL, targetR, l, mid, idx << 1);
        if (targetR > mid)ans += res(targetL, targetR, mid + 1, r, idx << 1 | 1);
        return ans;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }

    //建树
    build(1, n, 1);

    //轮询
    for (int i = 1; i <= m;i++) {
        cin >> sign;
        if (sign == 1) {
            cin >> x >> y >> k;
            update(x, y, 1, n, 1);
        }
        else {
            cin >> x >> y;            
            if (isFirst)isFirst = false;
            else cout << '\n';
            cout<< res(x, y, 1, n, 1);
        }
    }

    return 0;
}