POJ 1195 Mobile phones【树状数组二维】

迈不过友情╰ 2022-10-06 05:53 170阅读 0赞

题目大意

更新：一个矩阵的一个元素
    求和：求一个子矩阵元素和

学习了二维的树状数组
    和一维一样 
    只需要记住，对于矩阵A
    C[i][j]的表示的是 
    矩阵A[i][j]向左上分别延伸lowbit(i)和lowbit(j)个单位形成的子矩阵的和

#include <stdio.h>
    #include <iostream>
    
    using namespace std;
    
    #pragma warning(disable:4996)
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    #define low(x) ((x)&(-x))
    
    typedef long long ll;
    
    //ll a[1025][1025];
    ll c[1025][1025];
    
    ll s;
    
    bool update(ll x, ll y, ll A) { 
    	for (ll i=x; i <= s; i += low(i)) { 
    		for (ll j=y; j <= s; j += low(j)) { 
    			c[i][j] += A;
    		}
    	}
    	return true;
    }
    
    ll getS(ll x, ll y) { 
    	ll ret = 0;
    	for (ll i = x; i > 0 ; i -= low(i)) { 
    		for (ll j = y; j > 0; j -= low(j)) { 
    			ret += c[i][j];
    			
    		}
    	}
    	return ret;
    }
    
    int main() { 
    
    	//freopen("../in1.txt","r",stdin);
    	ll t;
    	memset(c, 0, sizeof(c));
    	while (cin >> t) { 
    
    		if (t == 0) { 
    			cin >> s;
    		}
    		else if (t == 1) { 
    			ll x, y, A;
    			cin >> x >> y >> A;
    			update(x + 1, y + 1, A);
    		}
    		else if (t == 2) { 
    			ll x1, y1, x2, y2;
    			cin >> x1 >> y1 >> x2 >> y2;
    			//debug(getS(x2 + 1, y2 + 1))
    			ll s = getS(x2+1,y2+1) - getS(x2+1,y1) - getS(x1,y2+1) + getS(x1,y1) ;
    			cout << s << endl;
    		}
    	}
    	
    	return 0;
    }

![在这里插入图片描述][20210611161502213.png]

--------------------

更新a\[1\]\[1\]示例：  
图片链接,侵删  
[https://www.docin.com/p-403698374.html][https_www.docin.com_p-403698374.html]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

[20210611161502213.png]: /images/20221005/d037d1cb8a1c443d9fb19972dd2a0164.png
[https_www.docin.com_p-403698374.html]: https://www.docin.com/p-403698374.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221005/0e66b2f6b80a4bffa7c2f508563b6161.png