线段树（1）——点修改&建树

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 10000

#define INF 2147000047

int n,m;

int minv[MAX],sumv[MAX];//附加信息

//温馨提示：这的附加信息最好开n*4的，原因自己画图推吧

int ql, qr;//查询区间

//查询[ql, qr]中的最小值

int query_min(int o, int L, int R) {

    int M = (L + R) >> 1, ans = INF;

    if(ql <= L && R <= qr) return minv[o];  //递归出口（当前节点完全在查询区间内）

    if(ql <= M)  ans = min(ans, query_min(o*2, L, M) );//往左走（查询区间在左儿子节点中有元素）

    if(M < qr) ans = min(ans, query_min(o*2+1, M+1, R) );//往右走（同理

    return ans;

}

//查询[ql, qr]元素和

int query_sum(int o, int L, int R) {

    int M = (L + R) >> 1 , ans = 0;

    if(ql <= L && R <= qr) return sumv[o];//出口

    if(ql <= M) ans += query_sum(o*2, L, M);

    if(qr > M) ans += query_sum(o*2+1, M+1, R);

    return ans;

}

int p,v;//修改A[p] = v

void update(int o, int L, int R) {

    int M = (L + R) >> 1;

    if(L == R) {

        minv[o] = v;

        sumv[o] = v;

		//....

    }

    else {// L < R

        //先递归更新左子树 或 右子树

        if(p <= M) update(o*2, L, M); else update(o*2+1, M+1, R);

        //然后计算本节点的附加值

        minv[o] = min(minv[o*2], minv[o*2+1]);

        sumv[o] = sumv[o*2] + sumv[o*2+1];

    }

} 

int main() {

    scanf("%d%d",&n,&m);

    for(p = 1; p <= n; p++) {

        scanf("%d", &v);

        update(1, 1, n);//建树

    }

    //注：可以换一种建树的方法，写一个build_tree（）之后一次性访问完所有节点，O(n)

//别忘了push_up

    for(int i = 1; i <= 15; i++) {

	   	printf("sumv[%d]  = %d, minv[%d] = %d\n", i, sumv[i], i, minv[i]);

	}

	int cmd;

	for(int i = 1; i <= m; i++) {

		scanf("%d",&cmd);

		if(cmd == 1) {

			scanf("%d%d",&ql,&qr);

			printf("[%d, %d]之间最小值为 %d\n",ql, qr, query_min(1, 1, n));

		}

		else {

			scanf("%d%d",&ql, &qr);

			printf("[%d, %d]之间的元素和为 %d\n",ql, qr, query_sum(1, 1, n));

		}

	}

    return 0;

}

/*

5 5

1 2 3 4 5

2 1 3

2 1 5

1 1 5

2 1 5

2 1 4

*/
巴特西

线段树（1）——点修改&建树

最新文章

热门文章
