면빈면빈면빈면빈

[적용한 알고리즘]

다익스트라

[아이디어]

기본 예제

[생각의 흐름 / 절차] 

내용

[교훈]

오랜만에 다익스트라를 봤다. 재밌었다.

<코드>

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 20001;
const int INF = 1000000000;
typedef pair<int, int> P;

int main(){
    int V, E, K;
    vector<P> adj[MAX_V];
    scanf("%d %d %d", &V, &E, &K);

    for (int i = 0; i < E; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        adj[from].push_back(P(to, cost));
    }

    int dist[MAX_V];
    int prev[MAX_V];
    fill(dist, dist + MAX_V, INF);
    bool visited[MAX_V] = { 0 };
    priority_queue<P, vector<P>, greater<P>> PQ;

    dist[K] = 0;
    PQ.push(P(0, K));

    while (!PQ.empty()){
        int cur;
        do {
            cur = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[cur]);

        if (visited[cur]) break;

        visited[cur] = true;

        for (auto &p : adj[cur]){
            int nxt = p.first;
            int nxt_cost = p.second;

            if (dist[nxt] > dist[cur] + nxt_cost){
                dist[nxt] = dist[cur] + nxt_cost;
                prev[nxt] = cur;
                PQ.push(P(dist[nxt], nxt));
            }
        }
    }

    for (int i = 1; i <= V; i++){
        if (dist[i] == INF) puts("INF");
        else printf("%d\n", dist[i]);
    }
    return 0;
}

[백준] 12015번 가장 긴 증가하는 부분 수열 2

의 코드도 동일하다.

[적용한 알고리즘]

세그먼트 트리, LIS

[아이디어]

세그먼트 트리!

[생각의 흐름 / 절차] 

내용

[교훈]

이거 풀려고 연산자 오버로딩을 공부했고,

세그먼트 트리의 원리를 정확히 깨우치려고 노력했음..

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool compare (pair<int, int> a, pair<int, int> b){
    if (a.first == b.first){ //첫번째 비교 대상이 같다면
        return a.second > b.second; //두번째 애를 비교해 큰 놈을 뒤로 보내준다.
    }
    else {
        return a.first < b.first;
    } // 오름차순으로 정렬해주세요
}

void update(vector<int> &tree, int node, int start, int end, int index, int delta){
    if (index < start || index > end) return; // 범위 밖에 있는 경우
    tree[node] = max(tree[node], delta);
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, delta);
        update(tree, node * 2 + 1, mid + 1, end, index, delta);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
int getMAX(vector<int> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return -1;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return max(getMAX(tree, node * 2, start, mid, left, right), getMAX(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a;

    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<int> tree(tree_size);

    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        a.push_back(make_pair(x, i));
    }

    sort(a.begin(), a.end(), compare);

    for (int i = 0; i < n; i++){
        int idx = a[i].second;
        int temp_max = getMAX(tree, 1, 0, n - 1, 0, idx);
        update(tree, 1, 0, n - 1, idx, temp_max + 1);
    }
    printf("%d", tree[1]);

    return 0;
}

[적용한 알고리즘]

세그먼트 트리, LIS

[아이디어]

[생각의 흐름 / 절차] 

내용

[교훈]

오래전부터 LIS 를 쓰면 풀리겠다고 생각했는데

도저히 N^2 의 DP로는 안풀려 잠깐 포기하고 있었던 문제였는데,

최근에 세그먼트 트리를 이용해서 풀 수 있다고 하여 

블로그를 보고 열심히 구현해봤다.

(http://kks227.blog.me/220791986409)

NlogN 으로 구현 가능한게 세그먼트 트리와 이분탐색이라는데, 

이분탐색을 이용하는 방법도 고민해봐야겠다.

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

bool compare (pair<int, int> a, pair<int, int> b){
    if (a.first == b.first){ //첫번째 비교 대상이 같다면
        return a.second > b.second; //두번째 애를 비교해 큰 놈을 뒤로 보내준다.
    }
    else {
        return a.first < b.first;
    } // 오름차순으로 정렬해주세요
}

void update(vector<int> &tree, int node, int start, int end, int index, int delta){
    if (index < start || index > end) return; // 범위 밖에 있는 경우
    tree[node] = max(tree[node], delta);
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, delta);
        update(tree, node * 2 + 1, mid + 1, end, index, delta);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
int getMAX(vector<int> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return -1;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return max(getMAX(tree, node * 2, start, mid, left, right), getMAX(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a;
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<int> tree(tree_size);

    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        a.push_back(make_pair(x, i));
    }

    sort(a.begin(), a.end(), compare);

    for (int i = 0; i < n; i++){
        int idx = a[i].second;
        int temp_max = getMAX(tree, 1, 0, n - 1, 0, idx);
        update(tree, 1, 0, n - 1, idx, temp_max + 1);
    }

    printf("%d\n", n - tree[1]);
    return 0;
}

[적용한 알고리즘]

세그먼트 트리

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

내용

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start]; // 리프 노드인 경우 자기 자신을 등록 시켜야함.
    }
    else {
        int mid = (start + end) / 2; // 아니라면 자기 밑에 자식을 더해야 함.
        return tree[node] = construct(a, tree, node * 2, start, mid) + construct(a, tree, node * 2 + 1, mid + 1, end);
    }
}

void update(vector<long long> &tree, int node, int start, int end, int index, long long delta){
    if (index < start || index > end) return; // 범위 밖에 있는 경우
    tree[node] += delta;
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, delta);
        update(tree, node * 2 + 1, mid + 1, end, index, delta);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
long long sum(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return 0;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n);
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<long long> tree(tree_size);

    construct(a, tree, 1, 0, n - 1);

    while (m--){
        int oper;
        scanf("%d", &oper);

        if (oper == 1){
            int x;
            long long y;
            scanf("%d %lld", &x, &y);

            long long delta = y - a[x - 1];
            a[x - 1] = y;
            update(tree, 1, 0, n - 1, x - 1, delta);
        }//update

        if (oper == 0){
            int left, right;
            scanf("%d %d", &left, &right);
            if (left > right) swap(left, right);
            printf("%lld\n", sum(tree, 1, 0, n - 1, left - 1, right - 1));
        }//sum
    }

    return 0;
}

[적용한 알고리즘]

세그먼트 트리

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

구간 합 구하기처럼 update 함수를 구성하면 안된다. 

앞으로 update 함수는 이렇게 써야지

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
#define mod 1000000007
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start]; // 리프 노드인 경우 자기 자신을 등록 시켜야함.
    }
    else {
        int mid = (start + end) / 2; // 아니라면 자기 밑에 자식을 더해야 함.
        return tree[node] = ((construct(a, tree, node * 2, start, mid) % mod) * (construct(a, tree, node * 2 + 1, mid + 1, end) % mod)) % mod;
    }
}

long long update(vector<long long> &tree, int node, int start, int end, int index, long long newVal){
    if (index < start || index > end) return tree[node]; // 범위 밖에 있는 경우
    if (start == end) return tree[node] = newVal;
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        return tree[node] = (update(tree, node * 2, start, mid, index, newVal) * update(tree, node * 2 + 1, mid + 1, end, index, newVal)) % mod;
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
long long mult(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return 1;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return (mult(tree, node * 2, start, mid, left, right) * mult(tree, node * 2 + 1, mid + 1, end, left, right)) % mod;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<long long> a(n);
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<long long> tree(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct(a, tree, 1, 0, n - 1);

    int t = m + k;
    while (t--){
        int oper;
        scanf("%d", &oper);

        if (oper == 1){
            int x;
            long long y;
            scanf("%d %lld", &x, &y);
            update(tree, 1, 0, n - 1, x - 1, y);
        }//update

        if (oper == 2){
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%lld\n", mult(tree, 1, 0, n - 1, left - 1, right - 1));
        }//sum
    }

    return 0;
}

[적용한 알고리즘]

세그먼트 트리

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

내용

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start]; // 리프 노드인 경우 자기 자신을 등록 시켜야함.
    }
    else {
        int mid = (start + end) / 2; // 아니라면 자기 밑에 자식을 더해야 함.
        return tree[node] = construct(a, tree, node * 2, start, mid) + construct(a, tree, node * 2 + 1, mid + 1, end);
    }
}

long long update(vector<long long> &tree, int node, int start, int end, int index, long long newVal){
    if (index < start || index > end) return tree[node]; // 범위 밖에 있는 경우
    if (start == end) return tree[node] = newVal;
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        return tree[node] = update(tree, node * 2, start, mid, index, newVal) + update(tree, node * 2 + 1, mid + 1, end, index, newVal);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
long long sum(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return 0;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n);
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<long long> tree(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct(a, tree, 1, 0, n - 1);

    while (m--){
        int sum_x, sum_y;
        long long change_idx, change_y;

        scanf("%d %d %lld %lld", &sum_x, &sum_y, &change_idx, &change_y);

        if (sum_x > sum_y) swap(sum_x, sum_y);
        printf("%lld\n", sum(tree, 1, 0, n - 1, sum_x - 1, sum_y - 1));

        update(tree, 1, 0, n - 1, change_idx - 1, change_y);
    }
    return 0;
}

[적용한 알고리즘]

X

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

연산자 오버로딩을 연습하기 위한 문제로..

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool compare (pair<int, int> a, pair<int, int> b){
    if (a.first == b.first){ //첫번째 비교 대상이 같다면
        return a.second < b.second; //두번째 애를 비교해 큰 놈을 뒤로 보내준다.
    }
    else {
        return a.first < b.first;
    } // 오름차순으로 정렬해주세요
}

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        a.push_back({x, y});
    }

    sort(a.begin(), a.end(), compare);

    for (int i = 0; i < n; i++){
        printf("%d %d\n", a[i].first, a[i].second);
    }

    return 0;
}

[적용한 알고리즘]

세그먼트 트리

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

세그먼트 트리 응용을 풀러 가야겠다.

더 간단하게 풀 수 있을 거 같은데..

<코드>

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long construct_min(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start];
    }
    else {
        int mid = (start + end) / 2;
        return tree[node] = min(construct_min(a, tree, node * 2, start, mid), construct_min(a, tree, node * 2 + 1, mid + 1, end));
    }
}
long long construct_max(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start];
    }
    else {
        int mid = (start + end) / 2;
        return tree[node] = max(construct_max(a, tree, node * 2, start, mid), construct_max(a, tree, node * 2 + 1, mid + 1, end));
    }
}

//left : 구하고 싶은 범위의 시작, right : 구하고 싶은 범위의 끝
long long SegmentTree_min(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start){
        return 1000000001;
    } // 범위를 벗어날 때
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return min(SegmentTree_min(tree, node * 2, start, mid, left, right), SegmentTree_min(tree, node * 2 + 1, mid + 1, end, left, right));
}

long long SegmentTree_max(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start){
        return -1;
    } // 범위를 벗어날 때
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return max(SegmentTree_max(tree, node * 2, start, mid, left, right), SegmentTree_max(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n);
    int h = (int) ceil(log2(n));
    int tree_size = (1 << (h + 1));
    vector<long long> tree_min(tree_size);
    vector<long long> tree_max(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct_min(a, tree_min, 1, 0, n - 1);
    construct_max(a, tree_max, 1, 0, n - 1);

    while (m--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%lld %lld\n", SegmentTree_min(tree_min, 1, 0, n - 1, x - 1, y - 1), SegmentTree_max(tree_max, 1, 0, n - 1, x - 1, y - 1));
    }

    return 0;
}

[적용한 알고리즘]

세그먼트 트리

[아이디어]

내용

[생각의 흐름 / 절차] 

내용

[교훈]

세그먼트 트리에서 update 함수가 빠진 모양

그냥 응용이었다.

<코드>

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start];
    }
    else {
        int mid = (start + end) / 2;
        return tree[node] = min(construct(a, tree, node * 2, start, mid), construct(a, tree, node * 2 + 1, mid + 1, end));
    }
}
//left : 구하고 싶은 범위의 시작, right : 구하고 싶은 범위의 끝
long long SegmentTree(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start){
        return 1000000001;
    } // 범위를 벗어날 때
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return min(SegmentTree(tree, node * 2, start, mid, left, right), SegmentTree(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n);
    int h = (int) ceil(log2(n));
    int tree_size = (1 << (h + 1));
    vector<long long> tree(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct(a, tree, 1, 0, n - 1);

    while (m--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%lld\n", SegmentTree(tree, 1, 0, n - 1, x - 1, y - 1));
    }

    return 0;
}

[적용한 알고리즘]

세그먼트 트리

[아이디어]

기본 문제래요

[생각의 흐름 / 절차] 

내용

[교훈]

어렵

<코드>

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start]; // 리프 노드인 경우 자기 자신을 등록 시켜야함.
    }
    else {
        int mid = (start + end) / 2; // 아니라면 자기 밑에 자식을 더해야 함.
        return tree[node] = construct(a, tree, node * 2, start, mid) + construct(a, tree, node * 2 + 1, mid + 1, end);
    }
}

void update(vector<long long> &tree, int node, int start, int end, int index, long long delta){
    if (index < start || index > end) return; // 범위 밖에 있는 경우
    tree[node] += delta;
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, delta);
        update(tree, node * 2 + 1, mid + 1, end, index, delta);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
long long sum(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return 0;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<long long> a(n);
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<long long> tree(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct(a, tree, 1, 0, n - 1);

    int t = m + k;
    while (t--){
        int oper;
        scanf("%d", &oper);

        if (oper == 1){
            int x;
            long long y;
            scanf("%d %lld", &x, &y);

            long long delta = y - a[x - 1];
            a[x - 1] = y;
            update(tree, 1, 0, n - 1, x - 1, delta);
        }//update

        if (oper == 2){
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%lld\n", sum(tree, 1, 0, n - 1, left - 1, right - 1));
        }//sum
    }

    return 0;
}

(19/11/23 수정)

delta 를 이용하는게 덧셈에서는 유용한데, 곱하기 나누기에서는 참 곤란하다. 그래서 그냥 newVal 을 넘겨주는 식으로 짜면 

코드도 더 직관적이고, 범용성도 넓어지는 것 같아서 이렇게 쓰려고 한다. (밑을 참고)

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

long long construct(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start]; // 리프 노드인 경우 자기 자신을 등록 시켜야함.
    }
    else {
        int mid = (start + end) / 2; // 아니라면 자기 밑에 자식을 더해야 함.
        return tree[node] = construct(a, tree, node * 2, start, mid) + construct(a, tree, node * 2 + 1, mid + 1, end);
    }
}

long long update(vector<long long> &tree, int node, int start, int end, int index, long long newVal){
    if (index < start || index > end) return tree[node]; // 범위 밖에 있는 경우
    if (start == end) return tree[node] = newVal;
    if (start != end){ //리프 노드가 아닌 경우
        int mid = (start + end) / 2;
        return tree[node] = update(tree, node * 2, start, mid, index, newVal) + update(tree, node * 2 + 1, mid + 1, end, index, newVal);
    }
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
long long sum(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
        return 0;
    }
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<long long> a(n);
    int tree_height = (int)ceil(log2(n));
    int tree_size = (1 << (tree_height + 1));
    vector<long long> tree(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct(a, tree, 1, 0, n - 1);

    int t = m + k;
    while (t--){
        int oper;
        scanf("%d", &oper);

        if (oper == 1){
            int x;
            long long y;
            scanf("%d %lld", &x, &y);
            update(tree, 1, 0, n - 1, x - 1, y);
        }//update

        if (oper == 2){
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%lld\n", sum(tree, 1, 0, n - 1, left - 1, right - 1));
        }//sum
    }

    return 0;
}