hdu1166 세그먼트 트리

3930 단어
세그먼트 트리는 구간의 찾기입니다. 만약 구간이 현재 세그먼트 트리 노드의 구간이 아니라면 왼쪽, 오른쪽으로 나누어 다시 찾아야 합니다.
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

const int maxn = 55555;
int a[maxn];
int tree[maxn << 2];// 4 

void pushUp(int curr) {
    tree[curr] = tree[2*curr] + tree[2*curr+1];
}

void buidTree(int left, int right, int curr) {// curr; left, right
    if (left == right) {
        tree[curr] = a[left];
        return;
    }

    int m = left + (right - left)/2;
   // if (m >= left)
        buidTree(left,m,2*curr);
   // if (m+1<=right)
        buidTree(m+1,right,2*curr + 1);

    pushUp(curr);

}

void update(int p, int add, int left, int right, int curr) {// p , add; curr, left, right; p , , 
    if (left == right) {
        tree[curr] += add;
        return;
    }

    int m = left + (right - left)/2;
    if (p <= m)
        update(p,add,left,m,2*curr);
    else
        update(p,add,m+1,right,2*curr + 1);

    pushUp(curr);

}

int query(int ql, int qr, int currLeft, int currRight, int curr) {// [ql,qr]
    if (ql <= currLeft && qr >= currRight) {
        return tree[curr];
    }
    int m = currLeft + (currRight - currLeft)/2;
    int sum = 0;
    if (ql <=m)
        sum = query(ql,qr,currLeft,m,2*curr);
    if (qr >m)
        sum += query(ql,qr,m+1,currRight,2*curr+1);
    
    return sum;
}

int main() {
    int t,n;
    scanf("%d", &t);
    for (int i = 0; i < t ; ++i ) {
        printf("Case %d:
",i+1); scanf("%d",&n); memset(a,0,sizeof(a)); for (int j = 1; j <= n; ++j ) scanf("%d",a + j); buidTree(1,n,1); char op[10]; while(scanf("%s",&op)) { if (op[0] == 'E') break; int a1,a2; scanf("%d%d",&a1,&a2); if (op[0] == 'Q') printf("%d
",query(a1,a2,1,n,1)); else if(op[0] == 'S') update(a1,-a2,1,n,1); else update(a1,a2,1,n,1); } } }
#include <iostream>
#include <stdio.h>

using namespace std;

const int maxn = 55555;
int a[maxn];
int tree[maxn<<2];// a , , 2*maxn+1 

void pushUp(int ind) {
	tree[ind] = tree[2*ind] + tree[2*ind+1];
}

void buildTree(int left, int right, int ind) {// , ind //left   right 
	if (left == right) {
		tree[ind] = a[left];
		return;
	}

	int mid = (left + right)/2;
	buildTree(left, mid, 2*ind);
	buildTree(mid+1, right, 2*ind + 1);
	pushUp(ind);

}

int query(int beg, int end , int left, int right, int ind){// beg, end ;left right 
	if (beg<=left && end >= right)
		return tree[ind];
	int mid = (left + right) / 2;
	int l = 0, r = 0;
	if (mid >= beg)
		l = query(beg,end,left,mid, 2*ind);
	if (mid < end)
		r = query(beg,end,mid +1,right, 2*ind+1);
	return l+ r;
}


void update(int pos, int value, int left, int right, int ind) {
	if(left == right) {
		tree[ind] += value;
		return;
	}

	int mid = (left + right) / 2;
	if (mid >=pos)
		update(pos, value, left, mid, 2*ind);
	else
		update(pos,value, mid + 1, right, 2*ind+1);

	pushUp(ind);
}


int main() {
	int t,n;
	scanf("%d", &t);

	for (int i = 0; i < t ; ++i)
	{
		printf("Case %d:
", i + 1); scanf("%d", &n); memset(a,0,sizeof(a)); for(int j = 1; j <= n; ++j) scanf("%d", a + j); buildTree(1,n, 1); char op[10]; while (scanf("%s", op)){ if (op[0] == 'E') break; int a1, a2; scanf("%d%d", &a1,&a2); if (op[0] == 'Q') printf("%d
", query(a1, a2,1,n,1)); else if(op[0] == 'S') update(a1,-a2,1,n,1); else update(a1,a2,1,n,1); } } }

좋은 웹페이지 즐겨찾기