hdu1166 세그먼트 트리
#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);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.