精华内容
下载资源
问答
  • 树状数组模板

    2017-11-08 21:39:24
    树状数组模板

    洛谷 P3374 【模板】树状数组 1
    洛谷 P3368 【模板】树状数组 2

    单点修改和区间查询

    洛谷 P3374 【模板】树状数组 1

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int n,m;
    int a[1000000],c[1000000];
    inline int read(){
        int x=0,w=1;char ch=0;
        while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
        if(ch=='-') w=-1,ch=getchar();
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();
        return x*w;
    }
    inline void add(int x,int y) { while(x<=n){ c[x]+=y; x+=x&-x; } }
    inline int getsum(int x){ int ans=0; while(x) { ans+=c[x]; x-=x&-x; } return ans;}
    int main(){
        n=read();m=read();
        for(register int i=1;i<=n;++i) a[i]=read(),add(i,a[i]);
        for(register int i=1;i<=m;++i) {
            int op=read(),x=read(),y=read();
            if(op==1) add(x,y);
            else if(op==2) printf("%d\n",getsum(y)-getsum(x-1));
        }
        return 0;
    } 
    

    区间修改和单点查询

    洛谷 P3368 【模板】树状数组 2

    #include<iostream>
    #include<cstdio>
    #define maxn 500100
    using namespace std;
    int n,m,c[maxn],a[maxn];
    inline int read(){
        int x=0,w=1;char ch=0;
        while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
        if(ch=='-') w=-1,ch=getchar();
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch-48),ch=getchar();
        return x*w;
    }
    inline int add(int x,int k){ for(int i=x;i<=n;i+=i&(-i)) c[i]+=k; }
    inline int query(int x) { int sum=0; for(int i=x;i>0;i-=i&(-i)) sum+=c[i]; return sum ;}
    int main(){
        n=read();m=read();
        for(int i=1;i<=n;i++)  a[i]=read();
        while(m--){
            int k=read();
            if(k==1){int x=read(),y=read(),z=read();add(x,z); add(y+1,-z);}//维护差分数组
            else{int x;x=read();printf("%d\n",a[x]+query(x));   }//query()求的是改变的值,再加上原来的值就可以了
        }
        return 0;
    }
    

    区间修改、区间查询

    参见lcf大佬的博客:https://www.cnblogs.com/lcf-2000/p/5866170.html
    另外一个大佬博客 https://www.cnblogs.com/RabbitHu/p/BIT.html

    展开全文
  • 树状数组』树状数组模板 竞赛需要用到的点 树状数组可以解决大部分基于区间上更新、查询的操作 树状数组能写的线段都能写,但线段能写的树状数组不一定能写 代码量小,且常数比线段树状数组是 与二...

    『树状数组』树状数组模板

    竞赛需要用到的点

    • 树状数组可以解决大部分基于区间上更新、查询的操作
    • 树状数组能写的线段树都能写,但线段树能写的树状数组不一定能写
    • 代码量小,且常数比线段树小
    • 树状数组是 二进制 的混合使用
    • lowbit(x) -> x&(-x) 为何? -x = x的二进制数中 0 变 1,1 变 0 然后末尾 + 1 lowbit可以得到一个由原二进制数变来的只有末尾1的新的二进制数

    树状数组略讲

    此处借用 百度百科 的图片

    960a304e251f95ca5e588459cf177f3e660952ab.jpg

    由此图我们可以得到以下信息(所有信息均用二进制处理)

    • 所有区间所包含的点的数量为 \(2^k\) 其中 \(k\) 为该数二进制下末尾 \(0\) 的个数

    • [单点修改] 当我们修改一个点 \(i\) 的值后,那么所包含 \(i\) 的区间都要改变

      • 哪些值要变? \(i\) 在二进制下,加上该二进制下最低位1 例如(1001 -> 1010)(9 -> 10)
    • [单点查询] 因为树状数组存储的形式类似于前缀和的形式,所以单点查询的办法也显而易见

      • 如何查询?查询 \(b_i\)\(b_{i - 1}\) 的值,然后两式相减 可得 \(a_i\)
    • [区间查询] 和单点查询类似 若查询\([i, j]\) ,那么可得 \(b_j - b_{i - 1}\)

    • [区间更新] 对于这种问题我们分两种情况

      • [区间修改&单点查询] 这里我们需要用到差分的思想,即将原本的树状数组的数组用差分数组来表示 \(b_i = a_i - a_{i - 1}\) ,答案也呼之欲出,对于差分 我们每次想得到 \(a_n\) 都是 \(\Sigma_{i = 1}^{n}b_i\) 然后对于每次修改,我们对 \(b_i\)\(b_j + 1\) 进行单点修改即可。

      • [区间修改&区间查询] 这里我们也要用到差分的思想,但这次我们需要维护两个差分数组(\(sum1\)\(sum2\))为什么? 我们从上面可以得到,想要知道 \(a_{[i, j]}\) 的和就得用以下式子求出,\(\Sigma_{i = 1}^na = \Sigma_{i = 1}^n\Sigma_{j = 1}^ib_j\) 激动人心的化简时刻到了\[\begin{eqnarray}\Sigma_{i = 1}^na &=& \Sigma_{i = 1}^n\Sigma_{j = 1}^ib_j \\&=& n\times b_1+(n-1)\times b_2 + (n - 2)\times b_3 + ... + b_n \\&=& n\Sigma_{i = 1}^nb_i - b_2-2b_3-3b_4-...-(n-1)b_n\\&=&n\Sigma_{i = 1}^nb_i + \Sigma_{i = 2}^n\Sigma_{j = 1}^{i - 1}(-b_i)\\&=&n\Sigma_{i = 1}^nb_i + \Sigma_{i = 2}^n(-b_i)\times (i - 1)\\&=&n\Sigma_{i = 1}^nb_i - \Sigma_{i = 2} ^ nb_i\times (i - 1)\end{eqnarray}\]

        因为 \(\Sigma_{i = 2}^nb_i\times (i - 1)\)\(\Sigma_{i = 1}^nb_i\times (i - 1)\) 等价
        所以原式子 = \(n\Sigma_{i = 1}^nb_i - \Sigma_{i = 1}^nb_i\times (i - 1)\) 在这个式子中,由于有\(\Sigma_{i = 1}^n\)所以我们可以易得用差分,用两个差分数组维护 \(b_i\)\(b_i \times (i - 1)\) 就可以了

    部分模板代码展现

    • 单点修改 单点查询
    #define fre yes
    
    #include <cstdio>
    
    const int N = 100005;
    int a[N], b[N];
    int n;
    
    int lowbit(int x) {
        return x & (-x);
    }
    
    void point_change(int x, int k) { // point_change(x, k)
        while(x <= n) {
            b[x] += k;
            x += lowbit(x);
        }
    }
    
    int getSum(int x) { // getSum(x) - getSum(x - 1)
        int res = 0;
        while(x > 0) {
            res += b[x];
            x -= lowbit(x);
        } return res;
    }
    
    int main() {
        ...
    }
    • 单点修改 区间查询
    #define fre yes
    
    #include <cstdio>
    
    const int N = 100005;
    int a[N], b[N];
    int n;
    
    int lowbit(int x) {
        return x & (-x);
    }
    
    void point_change(int x, int k) { // point_change(x, k)
        while(x <= n) {
            b[x] += k;
            x += lowbit(x);
        }
    }
    
    int getSum(int x) { // getSum(r) - getSum(l - 1)
        int res = 0;
        while(x > 0) {
            res += b[x];
            x -= lowbit(x);
        } return res;
    }
    
    int main() {
        ...
    }
    • 区间修改 单点查询
    #define fre yes
    
    #include <cstdio>
    
    const int N = 100005;
    int a[N], b[N];
    int n;
    
    int lowbit(int x) {
        return x & (-x);
    }
    
    void interval_change(int x, int k) { // point_change(l, x) point_change(r + 1, -x)
        while(x <= n) {
            b[x] += k;
            x += lowbit(x);
        }
    }
    
    int getSum(int x) { // getSum(x)
        int res = 0;
        while(x > 0) {
            res += b[x];
            x -= lowbit(x);
        } return res;
    }
    
    int main() {
        ...
    }
    • 区间查询 区间修改
    #define fre yes
    
    #include <cstdio> 
    
    const int N = 100005;
    int sum1[N], sum2[N];
    int n;
    
    int lowbit(int x) {
       return x & (-x); 
    }
    
    void interval_change(int j, int k) { 
        // push -> interval_change(i, a[i] - a[i - 1])
        // change -> interval_change(l, k) interval_change(r + 1, -k)
        int i = j;
        while(j <= n) {
            sum1[j] += k;
            sum2[j] += k * (i - 1);
            j += lowbit(j);
        }
    }
    
    int getSum(int i) { // getSum(r) - getSum(l - 1)
        int res = 0, x = i;
        while(i > 0) {
            res += x * sum1[i] - sum2[i];
            i -= lowbit(i);
        } return res;
    }
    
    int main() {
        ...
    }

    转载于:https://www.cnblogs.com/Nicoppa/p/11463495.html

    展开全文
  • 树状数组 模板

    2020-01-06 14:19:42
    P3374 【模板树状数组 1 #include<iostream> #include<cstdio> using namespace std; int a[100005], n, m; inline int lowbit(int x) { return x & (-x); } void add(int x, int s) { while (x...

    P3374 【模板】树状数组 1

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a[100005], n, m;
    inline int lowbit(int x) {
    	return x & (-x);
    }
    void add(int x, int s) {
    	while (x <= n) {
    		a[x] += s;
    		x += lowbit(x);
    	}
    }
    
    int sum(int x) {
    	int ans = 0;
    	while (x > 0) {
    		ans += a[x];
    		x -= lowbit(x);
    	}
    	return ans;
    }
    int main()
    {
    	int a, b, c;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i <= n; i++)
    	{
    		scanf("%d", &a);
    		add(i, a);
    	}
    	for (int i = 1; i <= m; i++)
    	{
    		scanf("%d%d%d", &a, &b, &c);
    		if (a == 1)
    			add(b, c);
    		else
    			printf("%d\n", sum(c) - sum(b - 1));
    	}
    	return 0;
    }
    
    

    P3368 【模板】树状数组 2

    用前n个数的和表示第n个数,修改x-y区间就相当于第x个数+a,第y+1个数-a。这样就跟普通的树状数组一样了。

    #include<iostream>
    #include<cstdio>
    using namespace std;
    long long a[500005], n, m;
    inline int lowbit(int x) {
    	return x & (-x);
    }
    void add(int x, long long s) {
    	while (x <= n) {
    		a[x] += s;
    		x += lowbit(x);
    	}
    }
    
    long long sum(int x) {
    	long long  ans = 0;
    	while (x > 0) {
    		ans += a[x];
    		x -= lowbit(x);
    	}
    	return ans;
    }
    int main()
    {
    	scanf("%d%d", &n, &m);
    	int k, x, y;
    	long long s, last(0);
    	for (int i = 1; i <= n; ++i) {
    		scanf("%lld", &s);
    		add(i, s - last);
    		last = s;
    	}
    	for (int i = 1; i <= m; ++i) {
    		scanf("%d", &k);
    		if (k == 1) {
    			scanf("%d%d%lld", &x, &y, &s);
    			add(x, s);
    			add(y + 1, -s);
    		}
    		else {
    			scanf("%d", &x);
    			printf("%lld\n", sum(x));
    		}
    	}
    	return 0;
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,572
精华内容 9,028
关键字:

树状数组模板