精华内容
下载资源
问答
  • 最近这几天学习了一下二维线段树二维线段树主要有两种写法,四分树和树套树,暂时还没写过四分树,因为这个东西确实不常用,而且不好写也不好调。 树套树的写法思路其实不难,首先我们知道,我们通常的线段树的...

    最近这几天学习了一下二维线段树,二维线段树主要有两种写法,四分树和树套树,暂时还没写过四分树,因为这个东西确实不常用,而且不好写也不好调。

    树套树的写法思路其实不难,首先我们知道,我们通常的线段树的操作都是在线段上进行的,即一维的,当推广到二维上,即矩阵时,我们就把它叫做二维线段树。

    二维线段树其实就是我们再操作时先找到对应x轴的区间(即第一维),之后再找到对应y轴的区间(即第二维),进行相应的操作。

    其实就是我们先给x轴上的每个点维护一颗线段树,然后我们再在x轴上的每个点里面再维护一颗线段树记录y轴。其实就是线段树的每一个节点又同时是一颗线段树,很明显的树套树做法。当然挺好理解的,就是码量挺大的,而且空间花销很大,很容易MLE。

    给出我的二维线段树(维护子矩阵最值和子矩阵求和和支持单点修改)的代码实现(可以当做模板来用):

    /*
        注意空间问题
        二维线段树求区间最值问题(可修)。
        给你一个n*n的初始矩阵,支持三种操作    
        单点修改某个位置的值(或者加上一个值)
        查询子矩阵最小值和最大值,或者查询子矩阵的和
        测试题目:hdu 4819 && poj 1195
    */
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define ll long long
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int N = 1024 + 5;
    ll MAX[N << 2][N << 2], minV, maxV,MIN[N<<2][N<<2];//维护最值
    ll a[N<<2][N<<2];//初始矩阵
    ll SUM[N<<2][N<<2],sumV;//维护求和
    int n;
    void pushupX(int deep, int rt)
    {
        MAX[deep][rt] = max(MAX[deep << 1][rt], MAX[deep << 1 | 1][rt]);
        MIN[deep][rt] = min(MIN[deep << 1][rt], MIN[deep << 1 | 1][rt]);
        SUM[deep][rt] = SUM[deep<<1][rt]+SUM[deep<<1|1][rt];
    }
    void pushupY(int deep, int rt)
    {
        MAX[deep][rt] = max(MAX[deep][rt << 1], MAX[deep][rt << 1 | 1]);
        MIN[deep][rt] = min(MIN[deep][rt << 1], MIN[deep][rt << 1 | 1]);
        SUM[deep][rt]=SUM[deep][rt<<1]+SUM[deep][rt<<1|1];
    }
    void buildY(int ly, int ry, int deep, int rt, int flag)
    {
        //y轴范围ly,ry;deep,rt;标记flag
        if (ly == ry){
            if (flag!=-1)
                MAX[deep][rt] = MIN[deep][rt] = SUM[deep][rt] = a[flag][ly];
            else
                pushupX(deep, rt);
            return;
        }
        int m = (ly + ry) >> 1;
        buildY(ly, m, deep, rt << 1, flag);
        buildY(m + 1, ry, deep, rt << 1 | 1, flag);
        pushupY(deep, rt);
    }
    void buildX(int lx, int rx, int deep)
    {
        //建树x轴范围lx,rx;deep
        if (lx == rx){
            buildY(1, n, deep, 1, lx);
            return;
        }
        int m = (lx + rx) >> 1;
        buildX(lx, m, deep << 1);
        buildX(m + 1, rx, deep << 1 | 1);
        buildY(1, n, deep, 1, -1);
    }
    void updateY(int Y, int val, int ly, int ry, int deep, int rt, int flag)
    {
        //单点更新y坐标;更新值val;当前操作y的范围ly,ry;deep,rt;标记flag
        if (ly == ry){
            if (flag) //注意读清楚题意,看是单点修改值还是单点加值
                MAX[deep][rt] = MIN[deep][rt] = SUM[deep][rt] = val;
            else pushupX(deep, rt);
            return;
        }
        int m = (ly + ry) >> 1;
        if (Y <= m)
            updateY(Y, val, ly, m, deep, rt << 1, flag);
        else
            updateY(Y, val, m + 1, ry, deep, rt << 1 | 1, flag);
        pushupY(deep, rt);
    }
    void updateX(int X, int Y, int val, int lx, int rx, int deep)
    {
        //单点更新范围x,y;更新值val;当前操作x的范围lx,rx;deep
        if (lx == rx){
            updateY(Y, val, 1, n, deep, 1, 1);
            return;
        }
        int m = (lx + rx) >> 1;
        if (X <= m)
            updateX(X, Y, val, lx, m, deep << 1);
        else
            updateX(X, Y, val, m + 1, rx, deep << 1 | 1);
        updateY(Y, val, 1, n, deep, 1, 0);
    }
    void queryY(int Yl, int Yr, int ly, int ry, int deep, int rt)
    {
        //询问区间y轴范围y1,y2;当前操作y的范围ly,ry;deep,rt
        if (Yl <= ly && ry <= Yr)
        {
            minV = min(MIN[deep][rt], minV);
            maxV = max(MAX[deep][rt], maxV);
            sumV += SUM[deep][rt];
            return;
        }
        int m = (ly + ry) >> 1;
        if (Yl <= m)
            queryY(Yl, Yr, ly, m, deep, rt << 1);
        if (m < Yr)
            queryY(Yl, Yr, m + 1, ry, deep, rt << 1 | 1);
    }
    void queryX(int Xl, int Xr, int Yl, int Yr, int lx, int rx, int rt)
    {
        //询问区间范围x1,x2,y1,y2;当前操作x的范围lx,rx;rt
        if (Xl <= lx && rx <= Xr){
            queryY(Yl, Yr, 1, n, rt, 1);
            return;
        }
        int m = (lx + rx) >> 1;
        if (Xl <= m)
            queryX(Xl, Xr, Yl, Yr, lx, m, rt << 1);
        if (m < Xr)
            queryX(Xl, Xr, Yl, Yr, m + 1, rx, rt << 1 | 1);
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%lld",&a[i][j]);
        buildX(1,n,1);
        int m;
        scanf("%d",&m);
        while(m--){
            int opt;
            scanf("%d",&opt);
            if(opt==1){ //单点修改
                int x,y,val;
                scanf("%d%d%d",&x,&y,&val);
                updateX(x,y,val,1,n,1);
            }
            else if(opt==2){//查询子矩阵最值,以及和
                minV=INF,maxV=-INF,sumV=0;//注意初始化
                int x1,y1,x2,y2;//注意看清楚给范围的方式以及下标是从0开始还是从1开始
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                queryX(x1,x2,y1,y2,1,n,1);
                printf("%lld %lld %lld\n",sumV,minV,maxV);
            }
            
        }
        return 0;
    }
    /*
    2 
    2 2
    2 2
    3
    2 1 1 2 2
    1 1 1 5
    2 1 1 2 2
    */

    下面给出一个我自己拉的在virtual judge上的二维线段树专题的链接:https://vjudge.net/contest/353513#overview

    展开全文
  • 二维线段树

    千次阅读 2020-02-07 00:07:14
    二维线段树本质上是树套树 因此无法实现 pushdownpushdownpushdown,用标记永久化替代 暂时无法满足任意模式的区间修改,也可能是我太菜了 注意修改后的 mergemergemerge,只针对所修改区间进行 mergemergemerge 即....

    维护一个矩阵,实现以下几个需求:
    ① : ①: 单点修改,区间查最值
    ② : ②: 区间加,区间查和
    ③ : ③: 区间修改(递增),区间查最值

    二维线段树本质上是树套树
    因此无法实现 p u s h d o w n pushdown pushdown,用标记永久化替代
    暂时无法满足任意模式的区间修改,也可能是我太菜了
    注意修改后的 m e r g e merge merge,只针对所修改区间进行 m e r g e merge merge 即可
    参考:线段树套线段树
    建树复杂度: O ( n 2 ) O(n^2) O(n2)
    单次修改查询复杂度: O ( l o g 2 n ) O(log^2n) O(log2n)


    例题一:Census UVA - 11297

    建树后,单点修改,区间查最大最小值

    // https://vjudge.net/problem/UVA-11297
    #include<bits/stdc++.h>
    #define rint register int
    #define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
    using namespace std;
    typedef long long ll;
    using pii = pair <int,int>;
    const int maxn = 5e2 + 5;
    int n, q;
    ll a[maxn][maxn];
    struct seg{
    	ll t1[maxn<<2], t2[maxn<<2], lz[maxn<<2];
    	void build(int L, int l, int r, int rt){
    		if(l == r) {
    			t1[rt] = t2[rt] = a[L][r];
    			return;
    		}
    		int m = l + r >> 1;
    		build(L, l, m, rt<<1);
    		build(L, m+1, r, rt<<1|1);
    		t1[rt] = max(t1[rt<<1], t1[rt<<1|1]);
    		t2[rt] = min(t2[rt<<1], t2[rt<<1|1]);
    	}
    	void update(int L, int R, ll x, int l, int r, int rt){
    		t1[rt] = t2[rt] = x;
    		if(l==L && r==R){
    			lz[rt] = x;
    			return;
    		}
    		int m = l + r >> 1;
    		if(m >= R) update(L, R, x, l, m, rt<<1);
    		else if(L > m) update(L, R, x, m+1, r, rt<<1|1);
    		else update(L, m, x, l, m, rt<<1), \
    			 update(m+1, R, x, m+1, r, rt<<1|1);
    		t1[rt] = max(t1[rt<<1], t1[rt<<1|1]);
    		t2[rt] = min(t2[rt<<1], t2[rt<<1|1]);
    	}
    	ll query1(int L, int R, int l, int r, int rt, ll sum){
    		if(l==L && r==R) return t1[rt];
    //		sum += lz[rt];
    		int m = l + r >> 1;
    		if(m >= R) return query1(L, R, l, m, rt<<1, sum);
    		else if(L > m) return query1(L, R, m+1, r, rt<<1|1, sum);
    		else return max( query1(L, m, l, m, rt<<1, sum), \
    						 query1(m+1, R, m+1, r, rt<<1|1, sum) );
    	}
    	ll query2(int L, int R, int l, int r, int rt, ll sum){
    		if(l==L && r==R) return t2[rt];
    //		sum += lz[rt];
    		int m = l + r >> 1;
    		if(m >= R) return query2(L, R, l, m, rt<<1, sum);
    		else if(L > m) return query2(L, R, m+1, r, rt<<1|1, sum);
    		else return min( query2(L, m, l, m, rt<<1, sum), \
    						 query2(m+1, R, m+1, r, rt<<1|1, sum) );
    	}
    } t[maxn<<2], lz[maxn<<2]; 
    
    void merge(seg &p, seg &p1, seg &p2, int L, int R, int l, int r, int rt){
    	if(l>R || r<L) return; 
    	p.t1[rt] = max(p1.t1[rt], p2.t1[rt]);
    	p.t2[rt] = min(p1.t2[rt], p2.t2[rt]);
    	if(l == r) return;
    	int m = l + r >> 1;
    	merge(p, p1, p2, L, R, l, m, rt<<1);
    	merge(p, p1, p2, L, R, m+1, r, rt<<1|1);
    }
    
    void build(int l, int r, int rt){
    	if(l == r){
    		t[rt].build(l, 1, n, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	build(l, m, rt<<1);
    	build(m+1, r, rt<<1|1);
    	merge(t[rt], t[rt<<1], t[rt<<1|1], 1, n, 1, n, 1);
    }
    void update(int x, int y, int xx, int yy, ll v, int l, int r, int rt){
    	t[rt].update(y, yy, v, 1, n, 1);
    	if(l==x && r==xx){
    		lz[rt].update(y, yy, v, 1, n, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	if(m >= xx) update(x, y, xx, yy, v, l, m, rt<<1);
    	else if(x > m) update(x, y, xx, yy, v, m+1, r, rt<<1|1);
    	else update(x, y, m, yy, v, l, m, rt<<1), \
    		 update(m+1, y, xx, yy, v, m+1, r, rt<<1|1);
    	merge(t[rt], t[rt<<1], t[rt<<1|1], y, yy, 1, n, 1);
    }
    ll query1(int x, int y, int xx, int yy, int l, int r, int rt, ll sum){
    	if(l==x && r==xx) return t[rt].query1(y, yy, 1, n, 1, 0);
    //	sum += lz[rt].query(y, yy, 1, n, 1, 0);
    	int m = l + r >> 1;
    	if(m >= xx) return query1(x, y, xx, yy, l, m, rt<<1, sum);
    	else if(x > m) return query1(x, y, xx, yy, m+1, r, rt<<1|1, sum);
    	else return max( query1(x, y, m, yy, l, m, rt<<1, sum), \
    					 query1(m+1, y, xx, yy, m+1, r, rt<<1|1, sum) );
    }
    ll query2(int x, int y, int xx, int yy, int l, int r, int rt, ll sum){
    	if(l==x && r==xx) return t[rt].query2(y, yy, 1, n, 1, 0);
    //	sum += lz[rt].query(y, yy, 1, n, 1, 0);
    	int m = l + r >> 1;
    	if(m >= xx) return query2(x, y, xx, yy, l, m, rt<<1, sum);
    	else if(x > m) return query2(x, y, xx, yy, m+1, r, rt<<1|1, sum);
    	else return min( query2(x, y, m, yy, l, m, rt<<1, sum), \
    					 query2(m+1, y, xx, yy, m+1, r, rt<<1|1, sum) );
    }
    
    int main() {
    	scanf("%d", &n);
    	for(int i=1; i<=n; i++)
    		for(int j=1; j<=n; j++)
    			scanf("%lld", &a[i][j]);
    	build(1, n, 1);
    	scanf("%d", &q);
    	while(q--){
    		char op; int x, y, xx, yy, w;
    		scanf(" %c", &op);
    		if(op == 'c') {
    			scanf("%d %d %d", &x, &y, &w);
    			update(x, y, x, y, w, 1, n, 1);
    		} else {
    			scanf("%d %d %d %d", &x, &y, &xx, &yy);
    			printf("%lld ", query1(x, y, xx, yy, 1, n, 1, 0));
    			printf("%lld\n", query2(x, y, xx, yy, 1, n, 1, 0));
    		}
    	}
    }
    

    例题二:Census UVA - 11297

    查询区间最大值,用最大值 + + + w w w 更新区间
    注意这里因为标记可以不断取 m a x max max,才可以实现区间更新

    // https://www.luogu.com.cn/problem/P3437
    #include<bits/stdc++.h>
    #define rint register int
    #define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
    using namespace std;
    typedef long long ll;
    const int maxn = 1e3 + 2;
    int d, s, q;
    struct seg{
    	int t[maxn<<2], lz[maxn<<2];
    	void build(int L, int l, int r, int rt){
    		if(l == r) {
    //			t[rt] = a[L][r];
    			return;
    		}
    		int m = l + r >> 1;
    		build(L, l, m, rt<<1);
    		build(L, m+1, r, rt<<1|1);
    		t[rt] = max(t[rt<<1], t[rt<<1|1]);
    	}
    	void update(int L, int R, int x, int l, int r, int rt){
    		t[rt] = max(t[rt], x);
    		if(l==L && r==R){
    			lz[rt] = max(lz[rt], x);
    			return;
    		}
    		int m = l + r >> 1;
    		if(m >= R) update(L, R, x, l, m, rt<<1);
    		else if(L > m) update(L, R, x, m+1, r, rt<<1|1);
    		else update(L, m, x, l, m, rt<<1), \
    			 update(m+1, R, x, m+1, r, rt<<1|1);
    //		t[rt] = max(t[rt<<1], t[rt<<1|1]);
    	}
    	int query(int L, int R, int l, int r, int rt){
    		if(l==L && r==R) return t[rt];
    		int m = l + r >> 1, ret = lz[rt];
    		if(m >= R) ret = max(ret, query(L, R, l, m, rt<<1));
    		else if(L > m) ret = max(ret, query(L, R, m+1, r, rt<<1|1));
    		else ret = max(ret, max( query(L, m, l, m, rt<<1), \
    						 query(m+1, R, m+1, r, rt<<1|1) ) );
    		return ret;
    	}
    } t[maxn<<2], lz[maxn<<2]; 
    
    void merge(seg &p, seg &p1, seg &p2, int l, int r, int rt){
    	p.t[rt] = max(p1.t[rt], p2.t[rt]);
    	if(l == r) return;
    	int m = l + r >> 1;
    	merge(p, p1, p2, l, m, rt<<1);
    	merge(p, p1, p2, m+1, r, rt<<1|1);
    }
    
    void build(int l, int r, int rt){
    	if(l == r){
    		t[rt].build(l, 1, s, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	build(l, m, rt<<1);
    	build(m+1, r, rt<<1|1);
    	merge(t[rt], t[rt<<1], t[rt<<1|1], 1, s, 1);
    }
    void update(int x, int y, int xx, int yy, int v, int l, int r, int rt){
    	t[rt].update(y, yy, v, 1, s, 1);
    	if(l==x && r==xx){
    		lz[rt].update(y, yy, v, 1, s, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	if(m >= xx) update(x, y, xx, yy, v, l, m, rt<<1);
    	else if(x > m) update(x, y, xx, yy, v, m+1, r, rt<<1|1);
    	else update(x, y, m, yy, v, l, m, rt<<1), \
    		 update(m+1, y, xx, yy, v, m+1, r, rt<<1|1);
    //	merge(t[rt], t[rt<<1], t[rt<<1|1], 1, s, 1);
    }
    int query(int x, int y, int xx, int yy, int l, int r, int rt){
    	if(l==x && r==xx) return t[rt].query(y, yy, 1, s, 1);
    	int m = l + r >> 1, ret = lz[rt].query(y, yy, 1, s, 1);
    	if(m >= xx) ret = max(ret, query(x, y, xx, yy, l, m, rt<<1));
    	else if(x > m) ret = max(ret, query(x, y, xx, yy, m+1, r, rt<<1|1));
    	else ret = max(ret, max( query(x, y, m, yy, l, m, rt<<1), \
    					 query(m+1, y, xx, yy, m+1, r, rt<<1|1) ) );
    	return ret;
    }
    
    int main() {
    	scanf("%d%d%d", &d, &s, &q);
    	while(q--){
    		int di, si, w, x, y;
    		scanf("%d %d %d %d %d", &di, &si, &w, &x, &y);
    		x++, y++;
    		w += query(x, y, x+di-1, y+si-1, 1, d, 1);
    		update(x, y, x+di-1, y+si-1, w, 1, d, 1);
    	}
    	printf("%d\n", query(1, 1, d, s, 1, d, 1));
    }
    

    例题三:Mosaic - HDU 4819

    建树后,查询区间最大最小值,单点更新

    // https://vjudge.net/problem/HDU-4819
    #include<bits/stdc++.h>
    #define rint register int
    #define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
    using namespace std;
    typedef long long ll;
    using pii = pair <int,int>;
    const int maxn = 8e2 + 5;
    int T, n, q;
    int a[maxn][maxn];
    struct seg{
    	int t1[maxn<<2], t2[maxn<<2], lz[maxn<<2];
    	void build(int L, int l, int r, int rt){
    		if(l == r) {
    			t1[rt] = t2[rt] = a[L][r];
    			return;
    		}
    		int m = l + r >> 1;
    		build(L, l, m, rt<<1);
    		build(L, m+1, r, rt<<1|1);
    		t1[rt] = max(t1[rt<<1], t1[rt<<1|1]);
    		t2[rt] = min(t2[rt<<1], t2[rt<<1|1]);
    	}
    	void update(int L, int R, ll x, int l, int r, int rt){
    		t1[rt] = t2[rt] = x;
    		if(l==L && r==R){
    			lz[rt] = x;
    			return;
    		}
    		int m = l + r >> 1;
    		if(m >= R) update(L, R, x, l, m, rt<<1);
    		else if(L > m) update(L, R, x, m+1, r, rt<<1|1);
    		else update(L, m, x, l, m, rt<<1), \
    			 update(m+1, R, x, m+1, r, rt<<1|1);
    		t1[rt] = max(t1[rt<<1], t1[rt<<1|1]);
    		t2[rt] = min(t2[rt<<1], t2[rt<<1|1]);
    	}
    	ll query1(int L, int R, int l, int r, int rt, ll sum){
    		if(l==L && r==R) return t1[rt];
    //		sum += lz[rt];
    		int m = l + r >> 1;
    		if(m >= R) return query1(L, R, l, m, rt<<1, sum);
    		else if(L > m) return query1(L, R, m+1, r, rt<<1|1, sum);
    		else return max( query1(L, m, l, m, rt<<1, sum), \
    						 query1(m+1, R, m+1, r, rt<<1|1, sum) );
    	}
    	ll query2(int L, int R, int l, int r, int rt, ll sum){
    		if(l==L && r==R) return t2[rt];
    //		sum += lz[rt];
    		int m = l + r >> 1;
    		if(m >= R) return query2(L, R, l, m, rt<<1, sum);
    		else if(L > m) return query2(L, R, m+1, r, rt<<1|1, sum);
    		else return min( query2(L, m, l, m, rt<<1, sum), \
    						 query2(m+1, R, m+1, r, rt<<1|1, sum) );
    	}
    } t[maxn<<2], lz[maxn<<2]; 
    
    void merge(seg &p, seg &p1, seg &p2, int L, int R, int l, int r, int rt){
    	if(l>R || r<L) return; 
    	p.t1[rt] = max(p1.t1[rt], p2.t1[rt]);
    	p.t2[rt] = min(p1.t2[rt], p2.t2[rt]);
    	if(l == r) return;
    	int m = l + r >> 1;
    	merge(p, p1, p2, L, R, l, m, rt<<1);
    	merge(p, p1, p2, L, R, m+1, r, rt<<1|1);
    }
    
    void build(int l, int r, int rt){
    	if(l == r){
    		t[rt].build(l, 1, n, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	build(l, m, rt<<1);
    	build(m+1, r, rt<<1|1);
    	merge(t[rt], t[rt<<1], t[rt<<1|1], 1, n, 1, n, 1);
    }
    void update(int x, int y, int xx, int yy, ll v, int l, int r, int rt){
    	t[rt].update(y, yy, v, 1, n, 1);
    	if(l==x && r==xx){
    		lz[rt].update(y, yy, v, 1, n, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	if(m >= xx) update(x, y, xx, yy, v, l, m, rt<<1);
    	else if(x > m) update(x, y, xx, yy, v, m+1, r, rt<<1|1);
    	else update(x, y, m, yy, v, l, m, rt<<1), \
    		 update(m+1, y, xx, yy, v, m+1, r, rt<<1|1);
    	merge(t[rt], t[rt<<1], t[rt<<1|1], y, yy, 1, n, 1);
    }
    ll query1(int x, int y, int xx, int yy, int l, int r, int rt, ll sum){
    	if(l==x && r==xx) return t[rt].query1(y, yy, 1, n, 1, 0);
    //	sum += lz[rt].query(y, yy, 1, n, 1, 0);
    	int m = l + r >> 1;
    	if(m >= xx) return query1(x, y, xx, yy, l, m, rt<<1, sum);
    	else if(x > m) return query1(x, y, xx, yy, m+1, r, rt<<1|1, sum);
    	else return max( query1(x, y, m, yy, l, m, rt<<1, sum), \
    					 query1(m+1, y, xx, yy, m+1, r, rt<<1|1, sum) );
    }
    ll query2(int x, int y, int xx, int yy, int l, int r, int rt, ll sum){
    	if(l==x && r==xx) return t[rt].query2(y, yy, 1, n, 1, 0);
    //	sum += lz[rt].query(y, yy, 1, n, 1, 0);
    	int m = l + r >> 1;
    	if(m >= xx) return query2(x, y, xx, yy, l, m, rt<<1, sum);
    	else if(x > m) return query2(x, y, xx, yy, m+1, r, rt<<1|1, sum);
    	else return min( query2(x, y, m, yy, l, m, rt<<1, sum), \
    					 query2(m+1, y, xx, yy, m+1, r, rt<<1|1, sum) );
    }
    
    int main() {
    	scanf("%d", &T);
    	for(int cas=1; cas<=T; cas++){
    		scanf("%d", &n);
    		for(int i=1; i<=n; i++)
    			for(int j=1; j<=n; j++)
    				scanf("%lld", &a[i][j]);
    		build(1, n, 1);
    		scanf("%d", &q);
    		printf("Case #%d:\n", cas);
    		while(q--){
    			int x, y, L;
    			scanf("%d %d %d", &x, &y, &L);
    			int x1 = max(x - L / 2, 1);
    			int x2 = min(x + L / 2, n);
    			int y1 = max(y - L / 2, 1);
    			int y2 = min(y + L / 2, n);
    			int mx = query1(x1, y1, x2, y2, 1, n, 1, 0);
    			int mi = query2(x1, y1, x2, y2, 1, n, 1, 0);
    			int w = (mx + mi) / 2;
    			printf("%d\n", w);
    			update(x, y, x, y, w, 1, n, 1);
    		}
    	}
    }
    

    例题四:SuperBrother打鼹鼠

    单点加,查询区间和
    注意这份代码也可以满足区间加,查询区间和

    #include<bits/stdc++.h>
    #define rint register int
    #define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
    using namespace std;
    typedef long long ll;
    using pii = pair <int,int>;
    const int maxn = 1024 + 5;
    int n;
    ll a[maxn][maxn];
    struct seg{
    	ll t[maxn<<2], lz[maxn<<2];
    	void build(int L, int l, int r, int rt){
    		if(l == r) {
    			t[rt] = a[L][r];
    			return;
    		}
    		int m = l + r >> 1;
    		build(L, l, m, rt<<1);
    		build(L, m+1, r, rt<<1|1);
    		t[rt] = t[rt<<1] + t[rt<<1|1];
    	}
    	void update(int L, int R, ll x, int l, int r, int rt){
    		if(l>R || r<L) return;
    		t[rt] += 1ll * x * (R - L + 1);
    		if(l==L && r==R){
    			lz[rt] += x;
    			return;
    		}
    		int m = l + r >> 1;
    		if(m >= R) update(L, R, x, l, m, rt<<1);
    		else if(L > m) update(L, R, x, m+1, r, rt<<1|1);
    		else update(L, m, x, l, m, rt<<1), \
    			 update(m+1, R, x, m+1, r, rt<<1|1);
    	}
    	ll query(int L, int R, int l, int r, int rt, ll sum){
    		if(l>R || r<L) return 0;
    		if(l==L && r==R) return t[rt] + sum * (r - l + 1);
    		sum += lz[rt];
    		int m = l + r >> 1;
    		if(m >= R) return query(L, R, l, m, rt<<1, sum);
    		else if(L > m) return query(L, R, m+1, r, rt<<1|1, sum);
    		else return query(L, m, l, m, rt<<1, sum) +
    					query(m+1, R, m+1, r, rt<<1|1, sum);
    	}
    } t[maxn<<2], lz[maxn<<2]; 
    
    void merge(seg p, seg p1, seg p2, int l, int r, int rt){
    	p.t[rt] = p1.t[rt] + p2.t[rt];
    	if(l == r) return;
    	int m = l + r >> 1;
    	merge(p, p1, p2, l, m, rt<<1);
    	merge(p, p1, p2, m+1, r, rt<<1|1);
    }
    
    void build(int l, int r, int rt){
    	if(l == r){
    		t[rt].build(l, 1, n, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	build(l, m, rt<<1);
    	build(m+1, r, rt<<1|1);
    	merge(t[rt], t[rt<<1], t[rt<<1|1], 1, n, 1);
    }
    void update(int x, int y, int xx, int yy, ll v, int l, int r, int rt){
    	if(l>xx || r<x) return;
    	t[rt].update(y, yy, 1ll * v * (xx - x + 1), 1, n, 1);
    	if(l==x && r==xx){
    		lz[rt].update(y, yy, v, 1, n, 1);
    		return;
    	}
    	int m = l + r >> 1;
    	if(m >= xx) update(x, y, xx, yy, v, l, m, rt<<1);
    	else if(x > m) update(x, y, xx, yy, v, m+1, r, rt<<1|1);
    	else update(x, y, m, yy, v, l, m, rt<<1), \
    		 update(m+1, y, xx, yy, v, m+1, r, rt<<1|1);
    }
    ll query(int x, int y, int xx, int yy, int l, int r, int rt, ll sum){
    	if(l>xx || r<x) return 0;
    	if(l==x && r==xx) return t[rt].query(y, yy, 1, n, 1, 0) + sum * (r - l + 1);
    	sum += lz[rt].query(y, yy, 1, n, 1, 0);
    	int m = l + r >> 1; ll ret = 0;
    	if(m >= xx) return query(x, y, xx, yy, l, m, rt<<1, sum);
    	else if(x > m) return query(x, y, xx, yy, m+1, r, rt<<1|1, sum);
    	else return query(x, y, m, yy, l, m, rt<<1, sum) +
    				query(m+1, y, xx, yy, m+1, r, rt<<1|1, sum) ;
    }
    
    int main() {
    	scanf("%d", &n);
    	while(1){
    		int m, x1, y1, x2, y2, w;
    		scanf("%d", &m);
    		if(m == 3) break;
    		if(m == 1){
    			scanf("%d%d%d", &x1, &y1, &w);
    			x1++, y1++, x2++, y2++;
    			update(x1, y1, x1, y1, w, 1, n, 1);
    		} else {
    			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    			x1++, y1++, x2++, y2++;
    			printf("%lld\n", query(x1, y1, x2, y2, 1, n, 1, 0));
    		}
    	} 
    }
    
    展开全文
  • 二维线段树专题

    万次阅读 2017-07-26 20:31:35
    二维线段树  二维线段树最主要用于平面统计问题。类似一维线段树,最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域...

    二维线段树

          二维线段树最主要用于平面统计问题。类似一维线段树,最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的方法是二维RMQ,但是二维RMQ不支持动态更新,所以二维线段树还是有用武之地的。
          如果对一维线段树已经驾轻就熟,那么直接来看下面两段对比,就可以轻松理解二维线段树了。
          一维线段树是一棵 二叉树,树上每个结点保存 一个区间和一个域,非叶子结点一定有 个儿子结点,儿子结点表示的 两个区间交集为空,并集为父结点表示的 区间;叶子结点的表示区间长度为1,即单位长度;域则表示了需要求的数据,每个父结点的域可以通过 两个儿子结点得出。
          二维线段树是一棵 四叉树,树上每个结点保存 一个矩形和一个域,非叶子结点一定有 二或四 个儿子结点,儿子结点表示的 四个矩形交集为空,并集为父结点表示的 矩形;叶子结点表示的矩形长宽均为1,域则表示了需要求的数据,每个父结点的域可以通过 四个儿子结点得出。
          一个4x3的矩形,可以用图1的树形结构来表示,给每个单位方块标上不同的颜色易于理解。
    图1
           图1中,每个叶子结点的单位面积为1,非叶子结点表示的矩形进行四分后,如图2所示,四个子矩形分别表示的是儿子结点表示的矩形区域。特殊的,当矩形面积为1 X H或者W X 1的时候,变成了一维的情况,这就是为什么有些结点有四个子结点,而有些结点只有两个子结点的原因了。
    图2
           基本结构已经清楚了,按照惯例,要介绍一下时空复杂度。
           首先来看空间复杂度,一个 W x H 的矩形,根结点表示的矩形是W x H,令N = max{W, H},那么这棵二维线段树的深度D = log2(N)+1,当这棵树是一棵满四叉树的时候,结点数达到最大值,根据等比数列求和公式,最大情况的结点数为 (4^D - 1) / 3。更加直观的,当N = W = H = 2^k, 必定是一棵满四叉树,结点数为(4^D-1) / 3 = ( 4^(k+1) - 1 ) / 3 = (2^(2k+2)-1) / 3,去掉分子上的零头1,约等于(4/3)*N^2, 所以空间复杂度为O(N^2)。
           再来看时间复杂度,需要分情况:
           建树:建树时必定访问到每个结点,而且都是访问一次,所以建树的复杂度为O(N^2);
           单点更新:每次更新一个单位矩形的值,访问时只会访问从树的根结点到叶子结点的一条路径,所以单点更新的复杂度为O( log2(N) )。
           区域询问:情况类似一维的区间询问。从根结点开始拆分区域,当询问区域完全覆盖结点区域时,不需要递归往下走,总体复杂度是 O( log2(N) * log2(N) )  ? 这里还是打个问号先,具体是一个log还是两个log记不清了,找个时间证明一下,可以肯定的是,不会退化成O(N)。
         
           接下来看看每个树结点需要保存一些什么信息, 以最值为例,除了保存最值以外,有可能需要知道这个最值在整个矩形的具体坐标,所以我们的最值信息dataInfo需要保存三个信息,posx和posy表示最值的具体位置,val保存最值,由于二维线段树的空间复杂度为O(N^2),所以坐标信息不会很大,为了尽力节省内存,坐标值用short来存即可。最值val的话看实际情况而定,一般用int就够了。
           treeNode则是线段树结点的结构体,其中成员由dataInfo对应的最值和son[4]表示的子结点编号组成,我们的线段树结点采用静态结点,即每个线段树结点都对应静态数组  nodes中的某个元素,便于通过编号在O(1)的时间内获取到对应树结点的指针,son[4]记录了四个子结点在nodes中的下标。仔细观察可以发现,如果对于一棵线段树,保证所有结点编号都连续的情况下,如果父结点的编号确定,那么子结点的编号也就确定了。例如,根结点编号为1,那么四个子结点编号为2、3、4、5,父结点编号为2,四个子结点的编号为6、7、8、9,根据数学归纳法,当结点编号为p,那么它的四个子结点编号为(4*p-2+x),其中x取值为[0, 3],所以四个子结点的编号信息可以通过O(1)的时间计算出来,就不用存储在线段树结点上了,大大节省了内存开销。
    结构定义代码如下:

    #define LOGN 10
    #define MAXN (1<<LOGN)
    #define MAXNODES 3*(1<<(2*LOGN)/+ 100)
    #define son(x) (p*4-2+x)
    // 最值信息
    struct dataInfo {
        short posx, posy;
        int val;
        dataInfo() {
            posx = posy =  val = -1;
        }
        dataInfo(short _posx, short _posy, int _val) {
            posx = _posx;
            posy = _posy;
            val = _val;
        }
    };
    // 线段树结点信息
    struct treeNode {
        // int son[4]
        dataInfo maxv, minv;
        void reset() {
            maxv = dataInfo(0, 0, INT_MIN);
            minv = dataInfo(0, 0, INT_MAX);
        }
    }nodes[ MAXNODES ];

    // 注意,这里需要返回指针,因为在后续使用中需要对这个结点的信息进行改变,如果返回对象的话只是一个copy,不会改变原结点的内容
    treeNode* getNode(int id) {
        return &nodes[id];
    }

           这时候,我们发现线段树的结点上还缺少一个很重要的信息,因为每个结点表示了一个矩形区域,那为什么没有存下这个矩形区域呢?毋庸置疑,也是为了节省内存,在接下来的区域查询、单点更新的介绍中会讲到,这个区域其实在每次递归的时候是作为传参进入函数内部的,结点编号确定,矩形区域就确定了,所以没必要存储在结点中。
           为了处理方便,我们还需要封装一个区间类(由于矩形可以表示成两个不同维度的区间,所以这里只需要封装一个区间类即可,矩形类的操作没有区间内那么简单,一目了然),它支持一些基本操作,如判交、判包含、取左右半区间等等、,具体代码如下:

    struct Interval {
        int l, r;
        Interval() {}
        Interval(int _l, int _r) {
            l = _l;
            r = _r;
        }
        // 区间中点 
        int mid() {
            return (+ r) >> 1;
        }
        // 区间长度 
        int len() {
            return r - l + 1;
        }
        // 左半区间 
        Interval left() {
            return Interval(l, mid());
        }
        // 右半区间 
        Interval right() {
            return Interval(mid()+1, r);
        }
        // 区间判交
        bool isIntersectWith( Interval& tarI ) {
            return !( l > tarI.|| r < tarI.);
        } 
        // 区间判包含
        bool isInclude( Interval& tarI ) {
            return l <= tarI.&& tarI.<= r;
        }
        bool in (int v) {
            return l <= v && v <= r;
        }
    };
            那么接下来就是建树了,建树就是递归生成结点的过程,这里的生成并非创建,原因是因为我们的结点是静态的。每建一次树,只是把所有线段树结点的信息进行一次重置,对于一个W x H的矩形,假定它的两个对角线坐标为(1, 1) - (W, H),那么我们首先将它切割成四个矩形,令WM = (1+W)/2, HM = (1+H)/2对角线坐标分别为:
            (1, 1) - (WM, HM)
            (WM+1, 1) - (W, HM)
            (1, HM+1) - (WM, H)
            (WM+1, HM+1) - (W, H)
            如图3所示,四个切割完后的矩形如下:
    图3
            这个切割过程是递归进行的,当某次切割的矩形为单位面积的时候,即为递归出口。当然还有一种情况,就是当某次切割后的矩形的某一维为1,而另一维大于1时,这里假设W = 1,H > 1,那么继续切割时会发现WM+1 > W,导致 (WM+1, 1) - (W, HM) 和 (WM+1, HM+1) - (W, H) 这两个矩形面积为负,所以在递归入口处需要判断是否有某一维的右端点小于左端点,如果有,这种矩形是不合法的,不能做为线段树的结点,不需要继续往下递归创建。
            
    建树代码如下:
    void build_segtree(int p, Interval xI, Interval yI) {
        // 空矩形(右端点小于左端点)
        if(xI.len() <= 0 || yI.len() <= 0) {
            return ;
        }
        treeNode* now = getNode(p);
        // 结点初始化
        now->reset();
        // 单位矩形
        if(xI.len() == 1 && yI.len() == 1) {
            return ;
        }
        build_segtree( son(0), xI.left(), yI.left() );
        build_segtree( son(1), xI.right(), yI.left());
        build_segtree( son(2), xI.left(), yI.right() );
        build_segtree( son(3), xI.right(), yI.right());   
    }
            其中p为当前线段树结点的编号,son(0) - son(3)则是作为子结点编号穿参进入切割后的矩形 getNode(p)用于获取编号为p的结点的结构指针,建树的目的就是为每个结点进行初始化,如果求的是最大值,那么将结点上的域都设成 INT_MIN ( 只要比所有接下来要插入的值小即可 ),如果求的是最小值,那么结点上的域都设成 INT_MAX( 只要比所有接下来要插入的值大即可 )。
            建树完毕后,这些结点都有了一个初始值,那么接下来就是需要在矩形的每个点插入一个值,然后更新线段树上每个结点的最值信息了。
            插入过程和建树过程的思想是一致的,同样是将矩形切割成四份,因为插入的是一个点,所以不可能同时存在于任意两个矩形中(因为是个矩形是互不相交的),所以每次四分只会选择一个矩形进行插入,为了让代码简介,我们还是先将矩形进行切割,然后模拟所有的矩形都能够插入,然后在递归入口处判断该点是否在矩形区域中,如果不在矩形区域直接返回。这样,当递归到单位矩形的时候,这个点的坐标一定是和矩形的坐标重合的,就可以直接更新该矩形所在的线段树结点的域信息了,更新完这个单位矩形还不够,还需要将信息传递给它的父结点,因为每次更新只有一个点,所以改变的结点只有从这个单位矩形所在结点到根结点的一条路径上的结点,所以复杂度是树的深度,即O(log2(N))。
    插入结点(单点更新)代码如下:
    bool insert_segtree(int p, Interval xI, Interval yI, int x, int y, int val) {
        if(xI.len() <= 0 || yI.len() <= 0) {
            return false;
        }
        if( !xI.in(x) || !yI.in(y) ) {
            return true;
        }
        treeNode *now = getNode(p);
        if(xI.len() == 1 && yI.len() == 1) {
            now->maxv = now->minv = dataInfo(x, y, val);
            return true;
        }
        bool isvalid[4];
        isvalid[0] = insert_segtree( son(0), xI.left(), yI.left(), x, y, val );
        isvalid[1] = insert_segtree( son(1), xI.right(), yI.left(), x, y, val );
        isvalid[2] = insert_segtree( son(2), xI.left(), yI.right(), x, y, val );
        isvalid[3] = insert_segtree( son(3), xI.right(), yI.right(), x, y, val ); 
       
        // 通过四个子结点的信息更新父结点 
        now->maxv = dataInfo(0, 0, MIN_VAL);
        now->minv = dataInfo(0, 0, MAX_VAL);
        int i;
        for(= 0;< 4; i++) {
            if( !isvalid[i] ) continue;
            treeNode *sonNode = getNode(son(i));
            now->maxv = sonNode->maxv.val > now->maxv.val ? sonNode->maxv : now->maxv;
            now->minv = sonNode->minv.val < now->minv.val ? sonNode->minv : now->minv;
        }
        return true; 
    }
           可以发现,插入的核心代码和建树是一致的,但是这里的插入操作,返回了一个值,表示的是当前插入的线段树结点p是否合法,因为我们在插入的时候无论如何都会将矩形切割成四份,没有去考虑上文中提到的有一维为1的情况,父结点的域值是通过子结点回溯上来进行更新的,如果子结点不合法,不应该作为更新的依据,所以作为父结点,需要知道哪些结点是不合法的。
           有了更新,当然需要询问,没有询问,更新也就失去了意义。
           询问一般是区域询问(单点询问就没必要用线段树了),如图4所示,在一个4 x 3的矩形中,需要询问灰色的矩形(3 x 2的矩形,以下统一称为询问矩形)中最大的数是什么。首先来说说原理,同样,和建树以及插入操作一样,我们首先不断将矩形进行切割,每当访问到一个结点的时候将询问矩形和结点矩形进行判交测试,一共有以下几种情况:
           1、询问矩形 和 结点矩形 没有交集 (图4中所有白色的叶子结点);
           2、询问矩形 完全包含 结点矩形 (图4中根结点的第三个子结点);
           3、询问矩形 不完全包含 结点矩形,并且存在交集(图4中根结点的第一、二、四个子结点);
           首先我们需要保存一个全局最大值信息,这个信息可以通过引用的方式传递到函数中去,在递归的过程中不断迭代更新;
           对于第1、2两种情况都是不需要继续往下递归的,第1种情况不会影响目前的最大值,第2种情况需要将结点上的最大值和全局最大值进行比较,保留大的那个;第三种情况有交集,所以我们需要将矩形继续分割,直到出现第1或者第2种情况为止,而且一定是可以出现的。
    图4
    区域询问代码如下:
    // query_type 0 最大值   1最小值
    void query_segtree(int p, Interval xI, Interval yI, Interval tarXI, Interval tarYI, dataInfo& ans, int query_type) {
        if(xI.len() <= 0 || yI.len() <= 0) {
            return ;
        }
       
        if( !tarXI.isIntersectWith(xI) || !tarYI.isIntersectWith(yI) ) {
            return ;
        }
        treeNode *now = getNode(p);
       
        // 最大值优化 
        if(query_type == 0 && ans.val >= now->maxv.val ) {
            return ;
        }
        // 最小值优化 
        if(query_type == 1 && ans.val <= now->minv.val) {
            return ;
        }
           
        if(tarXI.isInclude(xI) && tarYI.isInclude(yI)) {
            if(query_type == 0) {
                ans = now->maxv;
            }else {
                ans = now->minv;
            }
            return ;
        }
        query_segtree( son(0), xI.left(), yI.left(), tarXI, tarYI, ans, query_type );
        query_segtree( son(1), xI.right(), yI.left(), tarXI, tarYI, ans, query_type );
        query_segtree( son(2), xI.left(), yI.right(), tarXI, tarYI, ans, query_type );
        query_segtree( son(3), xI.right(), yI.right(), tarXI, tarYI, ans, query_type ); 
    }    
            这里加入了一个query_type,表示求的是最大值还是最小值,因为有的时候既需要知道最大值,又需要知道最小值,为了简化函数个数引入的一个变量。这里我们发现,当求最大值的时候,如果 询问矩形 和 结点矩形 是有交集并且并非完全包含的情况下,如果结点最大值比全局最大值(以上代码中的ans即全局最大值信息)还小,那么没必要再往下递归了,因为递归下去的最大值不会比当前结点的最大值大,这个优化很重要。
            以上就是二维线段树通过三个函数实现求区域最值的全部内容,建树 (build_segtree)、插入 ( insert_segtree )  询问 ( query_segtree ),其实当我们将这三个函数中的 yI 这个区间变成[1, 1]的时候,就变成了一维线段树的模板了。
    展开全文
  • 矩阵修改(二维线段树、矩形树)

    千次阅读 2017-03-13 20:55:52
    矩阵修改(二维线段树、矩形树)

    矩阵修改(二维线段树、矩形树)

    题目描述

    有一个n*m的矩阵(原始矩阵有值),现在可以对矩阵进行k次操作

    输入

    开始n行,每行m个整数,表示原始矩阵
    后k行每行先是一个字符表示操作类型,后跟4个整数,表示范围。若是修改操作还会给出1个整数表示修改值。
    操作分为三类:
    A x1 y1 x2 y2 val:表示对左上角为x1,y1,右下角为x2,y2的区域加上val
    S x1 y1 x2 y2 val:表示对左上角为x1,y1,右下角为x2,y2的区域减去val
    Q x1 y1 x2 y2:表示查询左上角为x1,y1,右下角为x2,y2的区域的和

    输出

    对于每次查询,输出结果。每个结果占一行

    数据规模

    n,m<=1000,k<=10000

    华丽的分界线

    引言

    其实就是一道二维线段树的裸题,但网上二维线段树的资源好像少的可怜,有的也只是树套树版本的,好像无法满足区间修改和区间查询。而且矩形树相对于树套树来说,在代码性能和写起来的难易程度上来说也要好上不少。主要是好理解,还有一维线段树的flg懒标记在矩形树上同样适用。

    Code思路

    先声明:这里矩形树的当做完全四叉树来做(方便计算儿子和父亲的下标)

    矩形树的代码其实跟一维线段树的写法差不多,只是由二叉变成了四叉而已。

    首先,一个节点定义为一个结构体,成员包括:坐标信息x1,y1,x2,y2(表示该节点的区间为以(x1,y1)为左上角(x2,y2)为右下角的矩形区域)和其他含义信息比如区间和sum,懒标记flg,区间最大值max,最小值min…什么的你自己根据需要去定就行了。

    结构体代码:

    const int MAXN = 1000;
    struct node{
        short x1, y1, x2, y2;
        int sum, flg;
    }T[MAXN * MAXN * 4];
    

    至于建树操作我们可以模仿,一维线段树的建树操作在x方向和y方向二分,如果x或y方向上长度为1了,那在该方向上就不在进行二分了。如果x,y方向上长度均为一了(即x1=x2且y1=y2),就说明到了树的最底层的单位节点了就可以返回了。

    建树代码:

    void build(int u, short x1, short x2, short y1, short y2){
        T[u].x1 = x1; T[u].x2 = x2;
        T[u].y1 = y1; T[u].y2 = y2;
        if(x1 == x2 && y1 == y2)
            return;
        short midx = (x1 + x2) >> 1;
        short midy = (y1 + y2) >> 1;
        if(x1 == x2){
            build(son1, x1, x2, y1, midy);
            build(son3, x1, x2, midy + 1, y2);
        }
        else if(y1 == y2){
            build(son1, x1, midx, y1, y2);
            build(son2, midx + 1, x2, y1, y2);
        }
        else{
            build(son1, x1, midx, y1, midy);
            build(son2, midx + 1, x2, y1, midy);
            build(son3, x1, midx, midy + 1, y2);
            build(son4, midx + 1, x2, midy + 1, y2);
        }
    }
    

    建树看懂了,这个代码就好写了,插入和查询跟一维线段树基本一样,这里就不单独写了,不懂的话就,看代码吧。

    Code

    #include<cstdio>
    #define son1 (u << 2) - 2
    #define son2 (u << 2) - 1
    #define son3 (u << 2)
    #define son4 (u << 2) | 1
    const int MAXN = 1000;
    struct node{
        short x1, x2, y1, y2;
        int sum, flg;
    }T[MAXN * MAXN * 2];
    
    int mp[MAXN + 5][MAXN + 5];
    
    template <class T>
    inline void Read(T &Ret){
        char ch; int flg = 1;
        while(ch = getchar(), ch < '0' || ch > '9')
            if(ch == '-') flg = -1;
        Ret = ch - '0';
        while(ch = getchar(), ch >= '0' && ch <= '9')
            Ret = Ret * 10 + ch - '0';
        ungetc(ch, stdin); Ret *= flg;
    }
    
    inline int sq(int u){return (T[u].x2 - T[u].x1 + 1) * (T[u].y2 - T[u].y1 + 1);}
    
    inline void pushdown(int u){
        if(!T[u].flg) return;
        if(T[son1].x1) T[son1].sum += sq(son1) * T[u].flg, T[son1].flg += T[u].flg;
        if(T[son2].x1) T[son2].sum += sq(son2) * T[u].flg, T[son2].flg += T[u].flg;
        if(T[son3].x1) T[son3].sum += sq(son3) * T[u].flg, T[son3].flg += T[u].flg;
        if(T[son4].x1) T[son4].sum += sq(son4) * T[u].flg, T[son4].flg += T[u].flg;
        T[u].flg = 0;
    }
    
    inline void pushup(int u){T[u].sum = T[son1].sum + T[son2].sum + T[son3].sum + T[son4].sum;}
    
    void build(int u, short x1, short x2, short y1, short y2){
        T[u].x1 = x1; T[u].x2 = x2;
        T[u].y1 = y1; T[u].y2 = y2;
        if(x1 == x2 && y1 == y2){
            T[u].sum = mp[x1][y1];
            return;
        }
        short midx = (x1 + x2) >> 1;
        short midy = (y1 + y2) >> 1;
        if(x1 == x2) build(son1, x1, x2, y1, midy), build(son3, x1, x2, midy + 1, y2);
        else if(y1 == y2) build(son1, x1, midx, y1, y2), build(son2, midx + 1, x2, y1, y2);
        else{
            build(son1, x1, midx, y1, midy);
            build(son2, midx + 1, x2, y1, midy);
            build(son3, x1, midx, midy + 1, y2);
            build(son4, midx + 1, x2, midy + 1, y2);
        }
        pushup(u);
    }
    
    void Insert(int u, short x1, short x2, short y1, short y2, int v){
        if(x2 < T[u].x1 || T[u].x2 < x1) return;
        if(y2 < T[u].y1 || T[u].y2 < y1) return;
        if(x1 <= T[u].x1 && T[u].x2 <= x2 && y1 <= T[u].y1 && T[u].y2 <= y2){
            T[u].sum += sq(u) * v;
            T[u].flg += v;
            return;
        }
        pushdown(u);
        Insert(son1, x1, x2, y1, y2, v);
        Insert(son2, x1, x2, y1, y2, v);
        Insert(son3, x1, x2, y1, y2, v);
        Insert(son4, x1, x2, y1, y2, v);
        pushup(u);
    }
    
    int getsum(int u, short x1, short x2, short y1, short y2){
        if(x2 < T[u].x1 || T[u].x2 < x1) return 0;
        if(y2 < T[u].y1 || T[u].y2 < y1) return 0;
        if(x1 <= T[u].x1 && T[u].x2 <= x2 && y1 <= T[u].y1 && T[u].y2 <= y2)
            return T[u].sum;
        pushdown(u);
        int res = 0;
        res += getsum(son1, x1, x2, y1, y2);
        res += getsum(son2, x1, x2, y1, y2);
        res += getsum(son3, x1, x2, y1, y2);
        res += getsum(son4, x1, x2, y1, y2);
        pushup(u);
        return res;
    }
    
    int main(){
        short n, m, a, b, c, d, k;
        int v;
        char id[3];
        Read(n); Read(m); Read(k);
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= m; ++ j)
                Read(mp[i][j]);
        build(1, 1, n, 1, m);
        while(k --){
            scanf("%s",id);
            Read(a); Read(b); Read(c); Read(d);
            switch(id[0]){
                case 'A': Read(v), Insert(1, a, c, b, d, v); break;
                case 'S': Read(v), Insert(1, a, c, b, d, -v); break;
                default: printf("%d\n",getsum(1, a, c, b, d));
            }
        }
        return 0;
    }
    
    
    展开全文
  • 思路:就是构造二维线段树,然后就是单点跟新,区间最值了。 /* 题意:给你一个矩阵,随后m行,x,y,l,从x行y列,扩大l/2个格子,不能出界,表示要查询的矩阵大小, 查询最小值与最大值,然后
  • 北京大学暑期ACM课程资源,留作备份.。
  • POJ - 2155 Matrix(二维线段树) Description Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 , j ). ...
  • 题解:模板题,使用二维线段树或者二维树状数组数组 以下给出2种做法: 1:二维树状数组 #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include...
  • 二维线段树 uva11992

    2017-12-10 00:42:11
    对于线段树,有了更深的了解,但是离熟悉还差的远。看模板 代码我可以看得懂,但是真正要盲打真的是有心无力。 思路:这道题的基本思路不难,有先成代码可以实现,不过要想到的关键点是:把一个矩阵看作是多个线段...
  • 二维线段树 题集

    千次阅读 2015-08-07 16:33:35
    一个二维矩阵初值为0,2个操作 1、某点(x,y)值增加val  2、查询子矩阵的和  #include #include #include #include #include #include using namespace std; #define ll long long #define rep( i
  • 二维线段树详解

    2019-08-17 00:06:54
    二维线段树最主要用于平面统计问题。类似一维线段树,最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的...
  • 二维线段树  二维线段树最主要用于平面统计问题。类似一维线段树,最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域...
  • HDU-4819: Mosaic(二维线段树(树套树)) 单点更新 区间查询
  • 二维线段树 题目链接:ybt金牌导航4-7-1 题目大意 给定一个正方形矩阵,每次询问一个指定矩阵的最大值最小值的平均值,再把这个矩阵的中心元素修改乘这个平均值。 思路 这题我可以知道如果只是线段的话就是线段树 **...
  • 二维线段树,支持单点更新、元素求和、查询最大值和最小值。代码:struct Nodey { int ly, ry, val, Max, Min, sum;//元素 最大值 最小值 元素和 }; int nx, ny;//横长 竖长 int posx[MAXN], posy[MAXN]; struct ...
  •  二维线段树就是在每个节点下再挂一科完整的线段树; #include #include #include #include const int M=4400; const int N=440; using namespace std; struct sub_node // 子线段树 { int la,ra...
  • 最多有20行, 可以建20棵线段树, 然后更新查询时按数维护 线段树区间合并, 两个lazy有主次之分(set比add优先) pushDown()和pushUp(); /* adrui's submission Language : C++ Result : Accepted Love : ll ...
  • 这还是我第一次打二维线段树(不是线段树套线段树) 首先我们对于绝对值可以考虑小的数被贡献多少次,那么就是找大的数的和-小的数的出现次数,那么我们就可以考虑把所有的数从小到大排序然后依次插入。 然后每个点...
  • 线段树 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std ; const int INF = ...
  • 二维线段树模板

    2018-11-01 17:02:00
    title: 二维线段树模板 date: 2018-10-31 15:21:44 tags: - 二维线段树 categories: “算法” 这个模板是根据HDU-4819编写的。功能是用二维线段树进行 二维点修改和区间查询最小者和最大值。 二维线段树的思想跟一维...
  • 题目大意: 二维区间里,某个矩形里都是01,...大致二维线段树就是这样的了…… 每个节点都是一个线段树。 QC大爷说二维线段树不支持打标记。好像这题也不用打标记了,只能标记永久化 //#i
  • 二维线段树(hdu1823)

    2019-03-17 21:03:00
    二维线段树其实也没有其他新知识,从名字上也能看出,他不过就是将一维变成二维,把之前的一维线段树每个节点再扩展成一棵线段树如下图: 图上红标号点是一维树,蓝标号点就是二维树。 从图也可看出,我们之所以...
  • RT贴个模板 http://paste.ubuntu.net/15334100/ 

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,366
精华内容 5,746
关键字:

二维线段树