精华内容
下载资源
问答
  • 树状数组 区间修改+区间查询 树状数组的区间修改和区间查询需要维护 两个 树状数组 首先还是先利用区间修改 单点查询用过的差分思想(将区间的修改操作变成单点的修改),我们先搞一个c数组作为差分数组 a数组是...

    树状数组 区间修改+区间查询

    树状数组的区间修改和区间查询需要维护 两个 树状数组

    首先还是先利用区间修改 单点查询用过的差分思想(将区间的修改操作变成单点的修改),我们先搞一个c数组作为差分数组

    c[i]=a[i]-a[i-1];  a数组是原数组,c数组是差分数组。

    简单可证:

    a[i]=c[1]+c[2]+c[3]+...+c[i];  

    即 a[1]=c[1],  a[2]=c[2]+c[1],  a[3]=c[3]+c[2]+c[1];

    那么可以得到以下式子:

    a[1]+a[2]+...+a[i]

    =c[1]+(c[1]+c[2])+...+(c[1]+c[2]+...+c[i])

    =i*c[1]+(i-1)*c[2]+...+c[i]

    =i*(c[1]+c[2]+...+c[i])-1*c[2]-...-(i-1)*c[i]

    于是,我们再搞一个数组c1

    c1[i]=(i-1)*c[i];

    那之前的式子就可以表示为

    a[1]+a[2]+...+a[i]=i*(c[1]+c[2]+...+c[i])-(c1[1]+c1[2]+...+c1[i]); 

    然后再搞两个树状数组来分别维护一下c数组和c1数组的区间和就ok了

    下面做一个类似的题目:codevs 1082的AC代码

    本题是一个裸题,非常的简单,读者可自行阅读理解,学会使用树状数组区间修改区间查询的方法

    #include<bits/stdc++.h>
    using namespace std;
    long long n,m,a[200010],b[200010],c[200010],bb[200010],c1[200010];
    long long lowbit(long long x)
    {
    	return x&-x;
    }
    void modify(int x,long long y)
    {
    	for (int i=x;i<=n;i+=lowbit(i))
    		b[i]+=y;
    }
    long long query(long long x)
    {
    	long long ans=0;
    	for (int i=x;i>0;i-=lowbit(i))
    		ans+=b[i];
    	return ans;
    }
    void modifyy(long x,long long y)
    {
    	for (int i=x;i<=n;i+=lowbit(i))
    		bb[i]+=y;
    }
    long long queryy(long long x)
    {
    	long long ans=0;
    	for (int i=x;i>0;i-=lowbit(i))
    		ans+=bb[i];
    	return ans;
    }
    int main()
    {
    	cin>>n;
    	for (int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		c[i]=a[i]-a[i-1];
    		c1[i]=(i-1)*c[i];
    	}
    	for (int i=1;i<=n;i++)
    		modify(i,c[i]);
    	for (int i=1;i<=n;i++)
    		modifyy(i,c1[i]);
    	cin>>m;
    	for (int i=1;i<=m;i++)
    	{
    		long long p;
    		cin>>p;
    		if (p==1)
    		{
    			long long xx,yy,zz;
    			cin>>xx>>yy>>zz;
    			modify(xx,zz);
    			modify(yy+1,-zz);
    			modifyy(xx,(xx-1)*zz);
    			modifyy(yy+1,-yy*zz);
    		}
    		if (p==2)
    		{
    			long long xx,yy,ss;
    			cin>>xx>>yy;
    			ss=(yy*query(yy)-queryy(yy))-((xx-1)*query(xx-1)-queryy(xx-1));
    			cout<<ss<<endl;
    		}
    	}
    	return 0;
    }
    

     

     

     

     

    展开全文
  • 树状数组:区间修改,区间查询树状数组 :区间修改,区间查询树状数组:区间修改,区间查询 一、树状数组是什么? 新手请参考 ————》》————》》————》》 树状数组 数据结构详解与模板(可能是最详细的了)...

    树状数组 :区间修改,区间查询

    一、树状数组是什么?

    新手请参考 ————》》

    树状数组 数据结构详解与模板(可能是最详细的了)

    夜深人静写算法(十三)- 树状数组

    二、区间修改与区间查询

    凡是涉及到区间修改,就必须用到 差分

    求前缀和:

    • apa_p 的前缀和:i=1pa[i]=i=1pj=1id[j]\sum_{i=1}^{p}a[i]=\sum_{i=1}^{p}\sum_{j=1}^{i}d[j]
    • i=1pj=1id[j]\sum_{i=1}^{p}\sum_{j=1}^{i}d[j]中,d1d_1 被用了 pp 次,d2d_2 被用了 p1p-1 次……那么我们可以写出:
    • apa_p 的前缀和:i=1pj=1id[j]=i=1pd[i](pi+1)=(p+1)i=1pd[i]i=1pd[i]i\sum_{i=1}^{p}\sum_{j=1}^{i}d[j]=\sum_{i=1}^{p}d[i]*(p-i+1)=(p+1)*\sum_{i=1}^{p}d[i]-\sum_{i=1}^{p}d[i]*i
    • 那么我们可以用树状数组维护两个数组的前缀和:一个数组是 sum1[i]=d[i]sum1[i]=d[i],另一个数组是 sum2[i]=d[i]isum2[i]=d[i]*i

    区间修改

    对于 t1t1 数组的修改同上对 dd 数组的修改。

    对于 t2t2 数组的修改也类似,我们给 t2[l]t2[l] 加上 l×xl \times x,给 t2[r+1]t2[r + 1] 减去 (r+1)×x(r + 1) \times x

    $区间修改

    ACcodeAC code

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int maxn=1e6+5;
    int n,q,a[maxn],maxx,b[maxn],c[maxn];
    
    /* --------------- fast io --------------- */ // begin
    namespace Fread
    {
        const int SIZE = 1 << 21;
        char buf[SIZE], *S, *T;
        inline char getchar()
        {
            if (S == T)
            {
                T = (S = buf) + fread(buf, 1, SIZE, stdin);
                if (S == T)
                    return '\n';
            }
            return *S++;
        }
    } // namespace Fread
    namespace Fwrite
    {
        const int SIZE = 1 << 21;
        char buf[SIZE], *S = buf, *T = buf + SIZE;
        inline void flush()
        {
            fwrite(buf, 1, S - buf, stdout);
            S = buf;
        }
        inline void putchar(char c)
        {
            *S++ = c;
            if (S == T)
                flush();
        }
        struct NTR
        {
            ~NTR() { flush(); }
        } ztr;
    } // namespace Fwrite
    #ifdef ONLINE_JUDGE
    #define getchar Fread ::getchar
    #define putchar Fwrite ::putchar
    #endif
    namespace Fastio
    {
        struct Doublee
        {
            double x;
            int k = 6;
        };
        struct Reader
        {
            template <typename T>
            Reader &operator>>(T &x)
            {
                char c = getchar();
                T f = 1;
                while (c < '0' || c > '9')
                {
                    if (c == '-')
                        f = -1;
                    c = getchar();
                }
                x = 0;
                while (c >= '0' && c <= '9')
                {
                    x = x * 10 + (c - '0');
                    c = getchar();
                }
                x *= f;
                return *this;
            }
            Reader &operator>>(double &num)
            {
                char in;
                double Dec = 0.1;
                bool IsN = false, IsD = false;
                in = getchar();
                if (in == EOF)
                {
                    return *this;
                }
                while (in != '-' && in != '.' && (in < '0' || in > '9'))
                {
                    in = getchar();
                }
                if (in == '-')
                {
                    IsN = true;
                    num = 0;
                }
                else if (in == '.')
                {
                    IsD = true;
                    num = 0;
                }
                else
                {
                    num = in - '0';
                }
                if (!IsD)
                {
                    while (in = getchar(), in >= '0' && in <= '9')
                    {
                        num *= 10;
                        num += in - '0';
                    }
                }
                if (in != '.')
                {
                    if (IsN)
                        num = -num;
                }
                else
                {
                    while (in = getchar(), in >= '0' && in <= '9')
                    {
                        num += Dec * (in - '0');
                        Dec *= 0.1;
                    }
                }
                if (IsN)
                {
                    num = -num;
                }
            }
            Reader &operator>>(char &c)
            {
                c = getchar();
                while (c == ' ' || c == '\n')
                {
                    c = getchar();
                }
                return *this;
            }
            Reader &operator>>(char *str)
            {
                int len = 0;
                char c = getchar();
                while (c == ' ' || c == '\n')
                {
                    c = getchar();
                }
                while (c != ' ' && c != '\n' && c != '\r')
                { // \r\n in windows
                    str[len++] = c;
                    c = getchar();
                }
                str[len] = '\0';
                return *this;
            }
            Reader() {}
        } cin;
        const char endl = '\n';
        struct Writer
        {
            Writer &operator<<(Doublee op)
            {
                static int n = pow(10, op.k);
                if (op.x == 0)
                {
                    putchar('0'), putchar('.');
                    for (int i = 1; i <= op.k; ++i)
                        putchar('0');
                    return *this;
                }
                if (op.x < 0)
                    putchar('-'), op.x = -op.x;
                long long y = (long long)(op.x * n) % n;
                op.x = (long long)op.x;
                cout << op.x;
                putchar('.');
                int bit[10], p = 0, i;
                for (; p < op.k; y /= 10)
                    bit[++p] = y % 10;
                for (i = p; i > 0; i--)
                    putchar(bit[i] + 48);
                return *this;
            }
            template <typename T>
            Writer &operator<<(T x)
            {
                if (x == 0)
                {
                    putchar('0');
                    return *this;
                }
                if (x < 0)
                {
                    putchar('-');
                    x = -x;
                }
                static int sta[45];
                int top = 0;
                while (x)
                {
                    sta[++top] = x % 10;
                    x /= 10;
                }
                while (top)
                {
                    putchar(sta[top] + '0');
                    --top;
                }
                return *this;
            }
            Writer &operator<<(char c)
            {
                putchar(c);
                return *this;
            }
            Writer &operator<<(char *str)
            {
                int cur = 0;
                while (str[cur])
                    putchar(str[cur++]);
                return *this;
            }
            Writer &operator<<(const char *str)
            {
                int cur = 0;
                while (str[cur])
                    putchar(str[cur++]);
                return *this;
            }
            Writer() {}
        } cout;
    } // namespace Fastio
    #define cin Fastio ::cin
    #define cout Fastio ::cout
    #define endl Fastio ::endl
    #define Doublee Fastio::Doublee
    /* --------------- fast io --------------- */ // end
    
    inline int lowbit(int a)
    {
    	return a&(-a);
    }
    inline void update(int x,int y)
    {
    	for(int i=x;i<=n;i+=lowbit(i))
    	{
    		b[i]+=y;
    		c[i]+=x*y;
    	}
    }
    inline void range_update(int l,int r,int x)
    {
    	update(l,x);
    	update(r+1,-x);
    }
    inline int query(int x)
    {
    	int ans=0;
    	for(int i=x;i;i-=lowbit(i))
    	{
    		ans += (x+1) * b[i] - c[i];
    	}
    	return ans;
    }
    inline int range_query(int l,int r)
    {
    	return query(r)-query(l-1);
    }
    signed main()
    {
    	cin>>n>>q;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		update(i,a[i]-a[i-1]);
    	}
    	for(int i=1;i<=q;i++)
    	{
    		int abc,x,y,z;
    		cin>>abc;
    		if(abc==1)
    		{
    			cin>>x>>y>>z;
    			range_update(x,y,z);
    		}
    		else
    		{
    			cin>>x>>y;
    			cout<<range_query(x,y)<<endl;
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 区间修改 任务: 对于数组a[1],a[2],a[3],….a[n],给定区间[l,r]。 要求将a[l]~a[r]的值都加v。 解决: 引入一个差分数组b,b[i]=a[i]-a[i-1](默认a[0]=0)。 比如: a:1,2,3,4,5 b: 1,1,1,1,1 ...

    区间修改

    任务:
    对于数组a[1],a[2],a[3],….a[n],给定区间[l,r]。
    要求将a[l]~a[r]的值都加v。
    解决:
    引入一个差分数组b,b[i]=a[i]-a[i-1](默认a[0]=0)。
    比如:
    a:1,2,3,4,5
    b: 1,1,1,1,1
    将区间[2,3]的值都加2
    a: 1,4,5,4,5
    b: 1,3,1,-1,1
    对于a中区间[l,r]都加v,b数组中b[l]+=v,b[r+1]-=v.
    故只需对原数组a的差分数组b用树状数组去进行单点修改,就可以快速地对数组a进行区间修改。

    单点查询

    任务:
    对进行了区间修改的数组进行单点查询
    解决:
    观察差分数组,可以推出:a[i]=b[1]+b[2]+…+b[i]。
    故只需求出原数组a的差分数组b的前缀i即可查询a[i]。

    区间查询

    任务:
    对进行了区间修改的数组进行区间查询
    解决:
    引入第二个数组c,c[i]=i*b[i].称为数组b的i倍数组。
    比如:
    a:1,2,3,4,5
    b:1,1,1,1,1
    c:1,2,3,4,5
    将区间[2,3]的值都加2后,
    a:1,4,5,4,5
    b:1,3,1,-1,1
    c:1,6,3,-4,5
    查询数组a的前3位数的和,即a[1]+a[2]+a[3]=1+4+5=10。
    a[1]+a[2]+a[3]=4*(b[1]+b[2]+b[3]) - (c[1]+c[2]+c[3])=4*5 - 10=10.
    设sumA表示数组a的前缀和,sumB表示数组b的前缀和,sumC表示数组c的前缀和。
    sumA[i]=(i+1)*sumB[i] - sumC[i]。
    上述公式其实是可以严格证明的。
    证明:
    假设要求数组a的前x项和。
    因为a[i]=b[1]+b[2]+…+b[i],
    a[1]+a[2]+a[3]+…+a[x]=b[1]+(b[1]+b[2])+(b[1]+b[2]+b[3])+…+(b[1]+b[2]+b[3]+…+b[x]).
    =b[1]x + b[2](x-1) + b[3](x-2) + b[i](x-i+1) +…+b[1]*x.
    所以需要b[x]一次,b[x-1]两次,b[x-2]三次,…,b[i] (x-i+1)次,b[1] x次。

    故只需用两个树状数组去维护原数组a的差分数组b的前缀和以及b的i倍数组c的前缀和即可得到原数组a的前缀和。

    展开全文
  • 区间修改,区间查询

    2017-10-20 17:56:06
    //区间修改,区间查询 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #define ll long long using namespace std; const int maxn = 100005; struct node { ll sum; int lazy; ...
    //区间修改,区间查询
    #define _CRT_SECURE_NO_WARNINGS
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string.h>
    #define ll long long
    using namespace std;
    
    const int maxn = 100005;
    struct node {
    	ll sum;
    	int lazy;
    }T[maxn<<2];
    
    void push_up(int root)
    {
    	T[root].sum = T[root << 1].sum + T[(root << 1) | 1].sum;
    }
    
    void push_down(int L, int R, int root)
    {
    	int mid = (L + R) >> 1;
    	T[root << 1].sum = T[root].lazy*(mid - L + 1);
    	T[root << 1 | 1].sum = T[root].lazy*(R - mid);
    	T[root << 1].lazy = T[root << 1 | 1].lazy = T[root].lazy;
    	T[root].lazy = 0;
    }
    
    void build(int l, int r, int root)
    {
    	if (l == r) {
    		scanf("%d", &T[root].sum);
    		return;
    	}
    	int mid=(l + r)>>1;
    	build(l, mid, root<<1);
    	build(mid + 1, r, root << 1 | 1);
    	push_up(root);   //不能遗漏这一步
    }
    
    void update(int l, int r,int value, int L, int R, int root)
    {
    	if (l <= L&&r >= R) {
    		T[root].lazy = value;
    		T[root].sum = value*(R - L + 1);
    		return;
    	}
    	int mid = (L + R) >> 1;
    	if (T[root].lazy)push_down(L, R, root);
    	if (r <= mid)update(l, r, value,L, mid, root << 1);
    	else if (l > mid)update(l, r, value, mid + 1, R, root << 1 | 1);
    	else {
    		update(l, r, value, L, mid, root << 1);
    		update(l, r, value, mid + 1, R, root << 1 | 1);
    	}
    	push_up(root);
    }
    
    
    
    int query(int l, int r, int L, int R, int root)
    {
    	if (l <= L&&r >= R)return T[root].sum;
    	int mid = (L + R) >> 1;
    	if (T[root].lazy)push_down(L, R, root);
    	if (r <= mid)return query(l, r, L, mid, root<<1);
    	else if (l > mid)return query(l, r, mid + 1, R, root<<1 | 1);
    	return query(l, mid, L, mid, root << 1) + query(mid + 1, r, mid + 1, R, root << 1 | 1);
    }
    
    int main()
    {
    	int n, q;
    	scanf("%d", &n);
    	build(1, n, 1);
    	scanf("%d", &q);
    	int a, b, c, d;
    	while (q--)
    	{
    		scanf("%d%d%d", &a, &b, &c);
    		if (a)
    		{
    			scanf("%d", &d);
    			update(b, c, d, 1, n, 1);
    		}
    		else printf("%d\n", query(b, c, 1, n, 1));
    	}
    
    	return 0;
    }
    

    展开全文
  • 区间修改+区间查询

    千次阅读 2018-07-23 11:13:46
    典型的区间修改+区间查询 题目如下: 链接:https://www.nowcoder.com/acm/contest/135/I 来源:牛客网   题目描述  Apojacsleam喜欢数组。  他现在有一个n个元素的数组a,而他要对a[L]-a[R]进行M次操作: ...
  • 线段树区间修改

    2021-05-08 19:59:08
    区间修改区间查询里面用到了一个lazytag方法 具体的意思就是:要修改某区间(L,R)的值时,不修改到底,而是修改到L<=begin&&R>=end时,直接对begin到end区间的和进行修改,修改后在次节点做一个标记...
  • 如果需要区间修改单点查询,可以差分解决 那么区间修改区间查询呢。 举个例子: a[1]~a[n]的数组,每次操作要么给a[l]~a[r]每个位置+x,要么查询a[l]~a[r]的和,操作数105 同样考虑差分,记c[i]=a[i]−a[i−1]c[i]...
  • 最一般树状数组能做到的操作...那么,如何同时做到区间求和,区间修改呢? 有人可能会说了,如果是区间求和区间修改的话,直接写线段树不就好了吗? 但是,从代码长度来看(dalao请无视),显然使用树状数组在考...
  • 对于一个数组b,用树状数组,我们可以通过维护它的差分数组a来区间修改单点查询。 现在有b的前缀和数组c。 我们如果要区间修改区间查询。 那么就探寻a和c的关系就行了。 发现每个a[i]会对每个i&amp;lt;=j的b...
  • C++ 区间修改

    2020-06-05 15:13:41
    c++的区间修改 题目描述: 有一个 N× M 的矩阵 A, 操作 add(x1,y1,x2,y2 , k)表示对矩阵 A 的(x1,y1) 到(x2,y2)区域内的每个 数都加上 k。 有 P 个 add 操作, 输出 P 个 add 操作后的矩阵 A。 输入格式: 第一...
  • 区间修改线段树

    2019-03-24 11:43:09
    区间修改线段树: 函数: 1、up向上传递 2、down父节点向下传递 3、modify区间修改(同时添加lazy标记) 4、query(与单点修改的差别是确认区间后要向下传递lazy标记) 代码: ///这个是区间求和的区间修改...
  • 线段树区间修改+区间查询

    千次阅读 2017-08-04 20:45:33
    大致思路:线段树的区间修改要比点修改难想一点。主要是多了一个延迟标记,目的是为了降低复杂度。但在询问的时候还需要把延迟标记逐个下放,还要更新原来的点,这就导致很难想了。 主要记住顺序: 要求区间修改 ...
  • C++线段树区间修改区间最大最小值模板 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int MAX=1e5+5; struct node { ll sum,lz;//...
  • 对于区间修改单点查询的问题,我们可以通过利用一个差分数组来标记增加的起点与终点,利用树状数组维护其前缀和即可得出每个位置的变化,即: \[ A_x=a_x+\sum_{i=1}^xb_i \] 那么对于区间修改区间查询则可以通过对...
  • 它功能强大,支持区间求和,区间最大值,区间修改,单点修改等操作。 线段树的思想和分治思想很相像。 线段树的每一个节点都储存着一段区间[L…R]的信息,其中叶子节点L=R。它的大致思想是:将一段大区间平均地...
  • //区间修改,区间查询 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #define ll long long using namespace std; const int maxn = 100005; struct node { ll sum; int lazy; ...
  • 数组数组区间修改+区间查询 在之前整理树状数组笔记时,已经将单点修改以及区间查询写的很清楚了。树状数组本质上就是一个可以在线 快速查询前缀和,并可以快速更新数值并维护的数据结构。我们喜欢用树状数组是因为...
  • 树状数组实现 区间修改+区间查询

    千次阅读 2017-08-04 20:17:12
    树状数组的本职:单值修改+区间查询 对于区间修改 首先想到的就是线段树 可是线段树的代码太tm长了 是真的懒得写 然后就学习了一下如何用树状数组实现 区间修改+区间查询
  • 听说树状数组可以支持区间加?...那现在假设你已经会了树状数组的 “ 单点修改,区间询问 ” ,我们就来讲一讲升级版的 “ 区间修改,区间询问 ” 【写在前面】 区间修改: 我们让 sigma (r ...
  • 介绍区间修改+区间查询之前一定要说一下区间修改+单点查询。 原本树状数组只能用于单点修改+区间查询。但是把原数组的差分数组做成树状数组就可以做到区间修改+单点查询。 即C[i]=A[i]-A[i-1](A[0]=0),然后把C...
  • 详解: http://www.cnblogs.com/lcf-2000/p/5866170.html比线段树更... 区间修改+单点查询维护差分数组即可; 但区间修改+区间查询需要维护两个树状数组;#include #include #include #include using namespace std;
  • 线段树模板题(二)——区间修改与查询区间和:区间修改区间求和 【题目描述】 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.求出某区间每一个数的和 【输入】 第一行包含两个...
  • 这是利用树状数组进行 区间求和区间修改,写起来比线段树轻松许多,具体的原理参考大佬博客:https://blog.csdn.net/fsahfgsadhsakndas/article/details/52650026 代码如下 1 /* 2 POJ 3468 树状数组 ...
  • 树状数组 树状数组是一种一般维护前缀和的数据结构。将数组进行差分后,树状数组还可以进行区间修改区间查询。
  • 普通的树状数组只资瓷单点修改和区间查询,首先要将其升级为区间修改 我们利用差分来进行 定义差分数组b[i]=a[i]-a[i-1] 这样$ a[j]=\sum_{i=1}^jb[i] $ 这样我们只要用树状数组维护一下b[i]的前缀和就好了 ...
  • 树状数组 区间修改

    2017-10-04 00:46:16
    树状数组 区间修改利用单点修改我们可以做到 1.单点加, 询问区间和 2.区间加, 询问单点值下面是关于树状数组的区间修改, 询问区间和 假设: aia_i是储存原数据的数组 令: xi=ai−ai−1 (a0=0)x_i=a_i-a_{i-1}\ \...
  • 题意要求:给定一个序列,支持区间修改和区间查询。 智障数据结构模板题…… 当然,题目名字告诉我们要用线段树。但是线段树很长,容易出现问题,而且跑得稍慢,所以就有dalao开始yy:可不可以让树状数组支持区间...
  • 线段树 区间修改

    2019-01-16 23:57:22
    我们对于线段树的区间修改你可以用一个最傻的办法循环进行单点修改(时间复杂度太高十分麻瓜)所以,我们要用一个聪明的做法** 延迟标记**(LAZY) 在限度拿书的“区间查询”指令中,每当遇到被询问区间[l,r]完全...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,101
精华内容 5,240
热门标签
关键字:

区间修改