[算法]线段树

[算法]线段树,第1张

[算法]线段树

P3372 【模板】线段树 1

#include
#include
#define ll long long
using namespace std;
const int  Maxn = 1000005;
ll d[4 * Maxn], tag[Maxn * 4];//注意该大小大概为所有单个值数量的四倍
ll a[Maxn];

inline void pushup(ll p) {//建树,先在pushup前面递归到最底层然后向上递归建树,确定节点值.
    //(p << 1) | 1意思是2*p+1,为了加快运算速度使用位运算
    d[p] = d[p << 1] + d[(p << 1) | 1];
}


inline void build(ll l, ll r, ll p) {//建立线段树
    if (l == r) {//如果以及递归到单个元素节点则开始返回,以单个节点为根本开始pushup
        d[p] = a[l];
        return;
    }
    ll mid = l + ((r - l) >> 1);//求中间值
    //递归
    build(l, mid, p << 1);//区间的左子节点
    build(mid + 1, r, (p << 1) | 1);//p<<1表示2*p 此时最后一位一定是0,或1,则相当于加1
    pushup(p);//建树求值
}

inline void pushdown(ll s, ll t, ll p) {//由更改的区间向下更改求值
    ll mid = s + ((t - s) >> 1);
    d[p << 1] += tag[p] * (mid - s + 1), d[(p << 1) | 1] += tag[p] * (t - mid);
    tag[p << 1] += tag[p], tag[(p << 1) | 1] += tag[p];  // 将标记下传给子节点
    tag[p] = 0;
    return;
}

inline void update(ll l, ll r, ll s, ll t, ll p, ll c) {//l,r 表示修改区间,[s, t] 为当前节点包含的区间,
    // p为当前节点的编号,c为要修改的值
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c;
        tag[p] += c;
        return;
    }// 当前区间为修改区间的子区间时直接修改当前节点的值,然后打标记,结束修改

    //如果不是,向下修改查询
    if (tag[p])
        pushdown(s, t, p);//先将上一次修改时tag中要修改的数向下修改
    int mid = s + ((t - s) >> 1);
    if (l <= mid)update(l, r, s, mid, p << 1, c);
    if (r > mid) update(l, r, mid + 1, t, (p << 1) | 1, c);
    pushup(p);//向上更改求值???
}
ll query(ll l, ll r, ll s, ll t, ll p)//查询l,r为要查询区间,st为当前节点所包含区间
{
    if (l <= s && t <= r)return d[p];//如果该节点已经是查询区间或完整的是查询区间中的一部分,则结束递归返回
    ll mid = s + ((t - s) >> 1);//求中值
    if (tag[p]) {//如果该区间有标记值,则向下查询前应先pushdown更新子区间的值
        pushdown(s, t, p);
    }
    ll ans = 0;//求解
    if (l <= mid)ans = query(l, r, s, mid, p << 1);//开始时ans无值可以直接赋值
    if (r > mid) ans += query(l, r, mid + 1, t, (p << 1) | 1);//要加上上面那行的值
    return ans;//返回
}


int main()
{
    ll n, m, e;
    ll x;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    build(1, n, 1);
    ll a1, b1, c1;
    while (m--)
    {
        scanf("%lld", &x);
        if (x == 1) {
            scanf("%lld%lld%lld", &a1, &b1, &c1);
            update(a1, b1, 1, n, 1, c1);
        }
        else {
            scanf("%lld%lld", &a1, &b1);
            printf("%lldn", query(a1, b1, 1, n, 1));
        }
    }
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5711733.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存