• 15이원준

# 3. 코드 ¶

## 3.1. 15이원준 ¶

### 3.1.1. 구간 합 구하기 4 ¶

```#include<iostream>

using namespace std;

long long int arr[4000000] = { 0, };
int start = 1;

int sort(int n){
while(n){
int p = (n-1) / 2;
if(n%2){
arr[p] = arr[n] + arr[(p+1)*2];
}
else{
arr[p] = arr[n] + arr[(p+1)*2 - 1];
}
n = p;
}
}
long long int initSort(int n){
if(n >= start){
return arr[n];
}
if(arr[n]){
if(arr[n] == -1){
return 0;
}
return arr[n];
}
long long int tmp1 = initSort((n+1)*2);
long long int tmp2 = initSort((n+1)*2 -1);
long long int tmp = tmp1 + tmp2;
if(tmp  == 0){
arr[n] = -1;
return 0;
}
return arr[n] = tmp;
}
long long int sum(int s, int e){
long long int ans = 0;
while(s < e){
if(s%2){
s = (s-1)/2;
}
else{
ans += arr[s];
s = s/2;
}
if(e%2){
ans += arr[e];
e = (e-2)/2;
}
else{
e = (e-1)/2;
}
}
if(s == e){
ans += arr[s];
}
return ans;
}

int main(){
int n,m,k;
cin>>n>>m;
while(n > start){
start *= 2;
}
start -= 1;
for(int i = 0; i<n; i++){
scanf("%d",&arr[start + i]);
}
initSort(0);
for(int i = 0; i< m; i++){
int tmp1, tmp2;
scanf("%d %d", &tmp1, &tmp2);
printf("%lld\n", sum(start-1 + tmp1, start-1+tmp2));
}
}
```

### 3.1.2. 구간 합 구하기 ¶

```#include<iostream>

using namespace std;

long long int arr[4000000] = { 0, };
int start = 1;

void sort(int n){
while(n){
int p = (n-1) / 2;
if(n%2){
arr[p] = arr[n] + arr[n+1];
}
else{
arr[p] = arr[n] + arr[n-1];
}
n = p;
}
}
long long int initSort(int n){
if(n >= start){
return arr[n];
}
if(arr[n]){
if(arr[n] == -1){
return 0;
}
return arr[n];
}
long long int tmp1 = initSort((n+1)*2);
long long int tmp2 = initSort((n+1)*2 -1);
long long int tmp = tmp1 + tmp2;
if(tmp  == 0){
arr[n] = -1;
return 0;
}
return arr[n] = tmp;
}
long long int sum(int s, int e){
long long int ans = 0;
while(s < e){
if(s%2){
s = (s-1)/2;
}
else{
ans += arr[s];
s = s/2;
}
if(e%2){
ans += arr[e];
e = (e-2)/2;
}
else{
e = (e-1)/2;
}
}
if(s == e){
ans += arr[s];
}
return ans;
}

int main(){
int n,m,k;
cin>>n>>m>>k;
while(n > start){
start *= 2;
}
start -= 1;
for(int i = 0; i<n; i++){
scanf("%d",&arr[start + i]);
}
initSort(0);

for(int i = 0; i< m+k; i++){
int tmp1, tmp2, tmp3;
scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
if(tmp1 == 1){
arr[start + tmp2 -1] = tmp3;
sort(start + tmp2 -1);
}
else{
printf("%lld\n", sum(start-1 + tmp2, start-1+tmp3));
}
}
}
```

### 3.1.3. 자두나무 ¶

```#include<iostream>
#include<algorithm>

using namespace std;

int arr[32][1001] = {0,};
int ina[1001] = {0,};
int main(){
int n, m;
cin>>n>>m;
for(int i = 1; i<=n; i++){
scanf("%d", &ina[i]);
}
int place = 1;
for(int i = 1; i<=m+1; i++){
for(int j = 1; j<=n; j++){
int tmp = arr[i][j-1];
if(ina[j] == place){
tmp++;
}
arr[i][j] = max(tmp, arr[i-1][j]);
}
if(i%2){
place = 2;
}
else{
place = 1;
}
}

cout<<arr[m+1][n];

}
```

# 4. 아이디어 ¶

## 4.1. 15이원준 ¶

• 구간합은 Binary Indexed Tree를 사용했습니다.
• 자두나무는 dp로 풀었습니다.(냅색을 약간 응용했습니다.)