종만북 공부내용(이라고 적었지만 10주 코딩테스트 완벽준비를 위한 issue)

[SHEWANTSME]

종만북을 시작해볼까.. ㅠ

[SHEWANTSME]

이 이슈를 만들었지만 정작 시작을 안했었구나,, ㅎㅎ

12월의 중간까지 왔지만,, 그동안 백준 티어 올리느라 제대로된 공부를 하지 않은것 같다.

그래서 새롭게 STL이랑 그 이상으로 알아야 할 알고리즘들을 정리해볼까 한다..

일단 기본적으로 알아야 할 STL내용을 적어보자면

---

Things you should know to master Algorithm Test

공부순서

1. stl 기초 (queue, stack, heap vector, deque, map, set)
2. stl 기초 알고리즘 ( 이분탐색, 정렬, )
3. Graph -> BFS,DFS
4. 브루트포스, 재귀호출
5. Greedy 기초
6. 다익스트라, 플로이드, 벨만포드
7. DP 1
8. 문자열 기초 (KMP, Manacher)
9. 수학1 : 정수론 기초
10. DP2 : 다차원 , 메모이제이션, 분할정복
11. 기하(geometry)
12. Graph -> SSC, 2-SAT
13. DP3 : bitmask , 기댓값
14. Network Flow, 이분매칭
15. segment tree와 bit
16. 문자열 응용 (아호 코라식, suffix array)
17. mcmf
18. DP 4 : knuth, CHT, D&C / 아호코라식dp/ 메모리사용량줄이기

// 이거까지 해도 최소 플레~다이아임

너의 상태를 보자면, 앞부분에서 뚫린 빵꾸를 제대로 매꾸지 않고 뒤에서 어정쩡하게 배우느라 존나 노답 그 자체임..

그래서 다시 basement부터 차근차근 할 필요성이 존나게 크다고 봄

---

각설하고

c++에서 내가 다시 다져야할 내용, stl이 뭐냐면

1.vector

2. queue
3. deque
4. map , multimap, unordered map ( unordered만 #include 다름)
5. set , multiset, unordered set ( unordered만 #include 다름)
6. stack
7. priority queue( by using heap)
8. pair ( 저 위에 애들쓸때 다 사용 가능함)
9. 구조체연습!

---

https://jasonyoo.tistory.com/45 -> 일단 stl 주요 내용 정리해둠 잘 읽어보쟝

[SHEWANTSME]

1주차 개념 강의 내용

1. 배열 1000만 넘어가면 의심 ㄱㄱ
2. 1000만 이상 필요하다 ? -> 이분탐색 ㄱㄱ
3. 재귀함수 -> BASE condition ( 무한재귀에 빠지지 않게 하기위한 condition) , Main Logic ( 점화식)
4. 누적합 -> prefix_sum ( 앞에서부터 더하는 누적 합) 을 주로 ( 99%) 사용!
5. "구간"에 대한 많은 "쿼리" -> TREE or 누적합 use

ex 1 :> 승철이문제

승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주며 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해보자.

입력

수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. 수는 100 이하의 자연수. 그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다.

출력

M개의 줄에 A부터 B까지의 합을 구하라.

범위

1 <= N <= 100,000

1 <= M <= 100,000

1 <= A <= B <= N

예제입력

8 3 1 2 3 4 5 6 7 8 1 4 1 5 3 5 에제출력

10 15 12

이렇게 풀면 시간초과 남

#include<bits/stdc++.h>
using namespace std;   
typedef long long ll;     
int a[100004], b, c, psum[100004], n ,m;
int main(){
    cin >> n >> m; 
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 0 ; i < m; i++){
        cin >> b >> c; 
        int sum = 0; 
        for(int j = b; j <= c; j++) sum += a[j];
        cout << sum << '\n'; 
    } 
    return 0;
}

그래서 이렇게 dp로 풀거나 구간합을 사용해야함

#include<bits/stdc++.h>
using namespace std;   
typedef long long ll;     
int a[100004], b, c, psum[100004], n ,m;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m; 
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i]; 
    }
    for(int i = 0 ; i < m; i++){
        cin >> b >> c; 
        cout << psum[c] - psum[b - 1] << "\n";
    } 
    return 0;
}

이게 구간합을 쓴거고(위에코드)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[100000];
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i == 1) dp[i] = x;
        else {
            dp[i] = x + dp[i - 1];
        } 
    }
    for (int i = 1; i <= m; i++) {
        int y, z; cin >> y >> z;
        if (y == 1) cout << dp[z] << endl;
        else {
            cout << dp[z] - dp[y - 1] << endl;
        }
        //cout << dp[z] - dp[y] << endl;
    }
    return 0;
}

위의 코드가 dp를 쓴건데 뭐 거의 같은 로직임

2번째 문제

// 문제 2.
#include <iostream>
#include<string>
#include <vector>
#include <stack>
#include <deque>
using namespace std;

int main() {
    string dopa = "life is limited";
    stack<char> stk;
    deque<char>dq;
    for (int j = 0; j < 3; j++) cout << dopa[j];

    cout << endl;

    for (int i = 0; i < dopa.size(); i++) {
        stk.push(dopa[i]);
        dq.push_back(stk.top());
    }
    while (!stk.empty()) {
        cout << stk.top() ;
        stk.pop();
    }

    cout << endl;

    string dopaa = "dopa!!";
    for (int i = 0; i < dopaa.size(); i++) {
        dq.push_front(dopaa[i]);
    }
    while (!dq.empty()) {
        cout << dq.back();
        dq.pop_back();
    }

    return 0;
}

나는 deque, stack, string까지 총동원해서 그냥 무지성으로 짰는데

그냥

#include<bits/stdc++.h>
using namespace std;
string dopa = "life is limited";
int main(){
      //문자열에서 부분배열(이 부분만을 끄집어낼 수 있겠죠?)
      cout << dopa.substr(0, 3) << "\n";
      // 반대로
      reverse(dopa.begin(), dopa.end());
      cout << dopa << "\n";
      // 추가한다.
      dopa += "dopa!!";
      cout << dopa << '\n';
      return 0;
} 

SUBSTR -> 짤라주는놈
REVERSE -> STRING을 돌려주는놈
STRING은 + - 연산 가능함 ㅎㅎ

이렇게 깔끔하게 나온다니.. ㅅㅂ

그러면 이렇게 나옴

/ lif detimil si efil detimil si efildopa!! /

// 참고로 STRING 관련 정리된 블로그는 https://blockdmask.tistory.com/333 https://blockdmask.tistory.com/338 이니까 잘 찾아보시게

[SHEWANTSME]

하.. 진짜 존나 빡친다. 개 잘정리해놨는데 다 날라감..

다시 적어보자 씨바

조합!! 다시 정리해두기!!

순열, 조합

(중복순열, 중복조합도 나중에 적을 예정)

1. 순열

맞다. 니가아는 그 순열 맞다

1.1 STL 사용하기 -> next_permutation과 prev_permutation 이 있다. -- > next는 오름차순, prev는 내림차순으로 먼저 sorted되어 있어야 한다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    // 5P2 출력 하는 코드

    vector<int> v = {1, 2, 3, 4, 5};

    int n = v.size();  // 5
    int r = 2  

    do
    {
      for(int i = 0; i < r; i++)
            cout << v[i] << " ";
        cout << '\n';

    reverse(v.begin() + r, v.end()); // 이게 굉장히 중요한데, reverse를 안시키면 nPn만 가능한 next_permu에서 
 // r만큼 떨어진곳부터 reverse 시켜주니까 역순으로 되어서 거기서부터는 아예 쳐다도 안보는거지!

    }while(next_permutation(v.begin(), v.end()));   

}
참고로 nPn이면 그냥 reverse 없애고 r자리에 n 넣으면 됨

아 그리고 next_permutation쓸때,

int a[10];
int main() {
    for (int i = 0; i < 9; i++) {
        cin >> a[i];
    }
    sort(a, a + 9);
    do {
        int sum = 0;
        for (int i = 0; i < 7; i++)sum += a[i];
        if (sum == 100) break;
    } while (next_permutation(a, a + 9));
    for (int i = 0; i < 7; i++) cout << a[i] << endl;
    return 0;
}
이렇게 arr로 쓰면 이런 느낌으로 하면 됨.

prev_permutation은 내림차순이고, 그냥 똑같은 논리로 하면 된다.

1.2 배열로 방문 check -> MOST COMMON WAY TO SOLVE THESE KIND OF PROBLEM

#include <iostream>
#include <vector>
using namespace std;
void Permutation(vector<bool> visited, vector<int> arr, vector<int> perm, int depth)
{ // 방문체크배열, 처음원소들어있던 배열, 최종 답이되는배열, 깊이
    if (depth == perm.size())  // r 
    { // 깊이가 == r(perm.size())일때
        for (int i = 0; i < perm.size(); i++)
            cout << perm[i] << " ";
        cout << endl;
        //출력
    }
    // 다른경우일때는
    for (int i = 0; i < arr.size(); i++)
    {
        if (visited[i]) continue;// visited[i] == true이면 건너뛰고

        visited[i] = true; // 방문 체크
        perm[depth] = arr[i];// 방문체크된 인덱스의 값이 perm[depth]
        Permutation(visited, arr, perm, depth + 1);
        visited[i] = false;  // 방문 해제
    }
}

int main()
{ // 지금은 3p3이라 이렇게 하는거지 char로 바꾸던 원소개수늘리던.. 다 됨
    vector<int> v = { 1,2,3};
    int n = v.size();
    int r = 3;
    vector<int>perm(r); // 최종 답이 되는 배열 ( 원래배열은 그 상태 유지해야하니까 새롭게 하나 make)
    vector<bool> visited(n); // 방문한것 체크
    Permutation(visited, v, perm, 0); // 3P3 배열의 모든 원소 출력

    return 0;
}

이해하기가 어렵긴 하지만 , perm[depth]랑 arr[i]가 항상 같은게 아니라서

일반적인 swap으로 하는 방식은 순서가 일정하지 않을 수 있어서 비추..

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
void Perm(int n, int r, int depth) {
    if (r == depth) {
        for (auto &ele : v) {
            cout << ele << " ";
        }cout << endl;
    }
    else {
        for (int i = depth; i < n; i++) {
            swap(v[i], v[depth]);
            Perm(n, r, depth + 1);
            swap(v[i], v[depth]);
        }
    }
}
int main() {
    v[0] = 1;
    v[1] = 2;
    v[2] = 3;
    Perm(3, 3, 0);
    return 0;
}

이게 swap이용한 방식

2. 조합

하.. 피곤하니까 나중에 정리하자 https://ansohxxn.github.io/algorithm/combination/

[SHEWANTSME]

2주차 내용 PART1

정점 ->Vertex 간선 ->Edge

Edge(간선) -> 이어주는놈 Vertex(정점) ->이음을 받는 놈 (Tree에서 노드라고도 함)

이런경우는 단방향

이런경우는 양방향이겠져

이렇게 나가는edge를 : OUTDEGREE라고 하고 들어오는 edge를 INDEGREE라고 함

이게 완전정리

가중치 (Cost)

Vertex랑 Edge 사이에 드는 비용 우리집에서 원캐까지 가는 시간이 10분 ->Cost = 10;

트리 (Tree)

->Cycle이 있으면 안되는 그래프!! (빙빙도는 형태가 되면 안됨) -> 무방향일때도 있고 방향이 있을때도 있음 -> 방향 있을때는 (DAG)라고 함(Directed Acyclic Graph) (밑의 그림이 DAG)

위의 놈처럼 이렇게 생김
--> DP 문제 풀 때 반드시 DAG가 쓰임! 알아두셈 ㅎ 백준 1697번풀때 -> 이거 dp아닌가? 싶었지만

DP는 DAG에 대해서만 사용해야 합니다. 이 문제처럼 정점의 방문 선후 관계가 명확하지 않은 경우에는 사이클에 의해 잘못된 답을 구할 수 있게 됩니다. 라고 하심 ㅎ

1. LEAF 노드 -> 제일밑에있는 초라한놈
2. Root 노드 ->맨 위에 있는 놈
3. Vertex -1 = Edge 라는 공식 성립
4. 임의의 두 개의 노드 사이의 경로는 “유일”+Exists. -> Can go Anywhere on tree Tree의 높이, 레벨이라고 부름( Level , height) 위의 트리는 Level = 3임. (루트노드의 레벨은 0 이라고 침)->문제마다 달라질 수 있음 ** 트리 안의 하위집합 ->subtree

Binary search tree (BST)

이렇게 생긴놈을 뜻함
노드의 왼쪽 subtree에는 반드시 노드보다 작은 값들이 오른쪽 subtree에는 노드보다 큰값들이 존재함!!

연결된 컴포넌트 ->(Connected Component)

이런식으로 보면 알거라고 본당 (위 그림은 CC가 3개임!)

[SHEWANTSME]

PART 2

GRAPH 표현 방법!

1. 인접행렬

   bool a[1004][1004];
   for(int i = 0;i < V; i++){
   for(int j = 0; j < V; j++){
       if(a[i][j]){
           cout << i << "부터 " << j << "까지 경로가 있습니다.\n";
       }
   }
   }

   이렇게 vertex와 edge의 관계를 나타내는 정사각형 행렬임. Mostly we use it as a boolean matrix ex) a[1][3] =1 ( 1에서 3으로 가는 경로 exist) 시복 :) O(V^2) 공복 :) O(V^2)

2. 인접리스트

   vector<int> adj[1004];
   adj[1].push_back(2); 
   adj[1].push_back(3);
   for(int i = 0;i < V; i++){
   for(int there : adj[i]){
   
   } 
   //위와 아래 코드는 의미가 같습니다. 
   for(int j = 0; j < adj[i].size(); j++){
       int there = adj[i][j];
   }
   }

   위와 같이 쓰이며, 3번노드 -> 5번노드 는 adj[3].push_back(5); 이렇게 씀

시복 :) O(V+E) 공복 :) O(V+E)

어지간하면 인접리스트로 생각하고, 행렬삘이다! 하면 인접행렬로 푸셈!

How to make directional Vector?

const int dx[4] = {0,1,-,1,0};
const int dy[4] = {1,0,0,-1};

여기서 방향의 제한을 if문으로 걸면 되겠죠? 문제마다 다르겠지만?

#include <bits/stdc++.h>
using namespace std; 
vector<int> adj[1004];
int main(){
    adj[1].push_back(2);
    adj[1].push_back(3);
    for(int there : adj[1]){
        cout << there << " ";
    } 
    return 0;
} 
// 2 3

DFS

깊이 우선탐색은 그래프를 탐색할 때 쓰이는 알고리즘으로써 특정한 노드에서 가장 멀리 있는 노드를 먼저 탐색하는 알고리즘입니다.

주어진 맵 전체를 탐색하며 한번 방문한 노드는 다시한번 방문하지 않기 때문에 만약 인접리스트로 이루어진 맵이면 O(V + E)이고 인접행렬의 경우 O(V^2)가 되졍

Pseudo code

DFS(G, u) 
    u.visited = true // u 원소는 visited배열에서 true
    for each v ∈ G.Adj[u] // Adj배열의 모든원소를 for
        if v.visited == false // visited해쓰면 false
            DFS(G,v)  // 아니면 DFS재귀

그림으로 보면 다음과 같다.

4 - 5 - 3 - 6 - 2 - 7 - 10 - 11 - 9 - 12 - 8 - 1

DFS를 구현하는 2가지 방법

1. 일단 방문체크

   void dfs(int here){
   visited[here] = 1; 
   for(int there : adj[here]){
       if(visited[there]) continue;
       dfs(there);
   }
   }

   2 . 일단 호출

void dfs(int here){
    if(visited[here]) return;
    visited[here] = 1;
    for(int there : adj[here]){ 
        dfs(there);
    }
}

일단 방문이 되어있던 안되어있던 호출부터 함 -> 방문되어있다면 return해서 함수 종료시킴

BFS

BFS는 그래프를 탐색하는 알고리즘이며 노드에서 시작해 이웃한 노드들을 먼저 탐색하는 알고리즘이자 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰입니다. 시간복잡도는 DFS와 같으며 주어진 맵전체를 탐색하며 한번 방문한 노드는 다시한번 방문하지 않기 때문에 만약 인접리스트로 이루어진 맵이면 O(V + E)이고 인접행렬의 경우 O(V^2)가 됩니다.

참고로 가중치가 다른 그래프 내에서 최단거리 알고리즘은 다익스트라, 벨만포드 등을 써야 합니다.

--> BFS는 queue가 무조건 필요함 , 물론 visited배열도 필요하지요.

BFS를 구현하는 2가지 방법

1. BFS(G, u)
   u.visited = true // u원소는 방문했다고 함
   q.push(u); // queue에 u를 push
   while(q.size()) // 만약 q가 empty하지 않을때까지 = while(not q.empty())
       u = q.front() //queue의 맨앞놈을 u 라고 하고
       q.pop() // 빼버린다음
       for each v ∈ G.Adj[u] // u를 중심으로 인접노드 탐색.
           if v.visited == false // 방문 안한놈을 
               v.visited = true // 방문했다고 하고
               q.push(v)  // queue에 push

2. (거의 비슷함 위에거랑) -> We do use this code style mostly.

BFS(G, u)
    u.visited = 1
    q.push(u);
    while(q.size()) 
        u = q.front() 
        q.pop()
        for each v ∈ G.Adj[u]
            if v.visited == false
                v.visited = u.visited + 1 // 이거가 달라진거임
                q.push(v)

최단거리 배열을 v.visited = u.visited +1 로 함으로써, 지금 있는곳에서 +1을 하면 가야할 곳 까지의 최단거리가 되겠구나!를 인식해야함. -> which means you can search through level(height)

이렇게 말이야 ㅎㅎ.

이거를 보면 알수 있지 그러면 최종적으로

이렇게 되고 가중치가 같은 최단거리 ---> BFS!! 항상 염두해 두자!

최종정리 :

-->

이름	설명
DFS	메모리 덜씀 , 절단점등 문제에 사용, 스택오버헤드 조심!, 코드 더 짧음 , 완탐에서 주로 씀
BFS	메모리 더씀, 가중치 같은 그래프의 최단거리 , 코드 더 김

전형적인 DFS , BFS는 정말 외우고 있을 정도로 빨리 짜둬야 한다!!

void DFS(int y , int x){
visited [y][x] = 1; // 시작부터 걸던가 
for(int i=0 ; i<4; i++){
    int ny = y+dy[i];
    int nx = x + dx[i];
    if(nx>=0 and ny>=0 and nx<10 and ny < 10)
        //visited[ny][nx]=1;    -> visited를 여기다 걸던가
        DFS(ny, nx)
    }
}

void BFS(int y, int x){
  visited[y][x] = 1;
  q.push({y,x});
  while(not q.empty()){
  tie(y,x) = q.front(); q.pop(); // tie를 쓰면 좀 더 빨리 코딩가능!
    for(int i=0 ; i<4; i++){
    int ny = y+dy[i];
    int nx = x+dx[i];
    if(~~~~ checking Overflows){
        visited[ny][nx] = visited[y][x];
        q.push({ny,nx});
    }
  }
}

기본적인것들을 외워야 응용을 할 수 있다링!!!

[SHEWANTSME]

PART 3.

트리 순회

1. 후위 (post-order)

   postorder( node )
   if (node.visited == false) 
       postorder( node->left ) 
       postorder( node->right )
       node.visited = true  # 얘가 중간이면 중위 얘가 맨앞이면 전위 ,,크게 특별한것도 없음
   ​

   얘를 post, in, pre로 출력해보면 다음과 같다

#include <bits/stdc++.h>
using namespace std; 
vector<int> adj[1004]; 
int visited[1004];

void postOrder(int here){ 
    if(visited[here] == 0){ 
        if(adj[here].size() == 1)postOrder(adj[here][0]);
        if(adj[here].size() == 2){
            postOrder(adj[here][0]); 
            postOrder(adj[here][1]);
        }
        visited[here] = 1; 
        cout << here << ' ';
    } 
} 
void preOrder(int here){
    if(visited[here] == 0){
        visited[here] = 1; 
        cout << here << ' ';
        if(adj[here].size() == 1)preOrder(adj[here][0]);
        if(adj[here].size() == 2){
            preOrder(adj[here][0]); 
            preOrder(adj[here][1]);
        }
    }
}  
void inOrder(int here){     
    if(visited[here] == 0){ 
        if(adj[here].size() == 1){ 
            inOrder(adj[here][0]); 
            visited[here] = 1; 
            cout << here << ' ';
        }else if(adj[here].size() == 2){
            inOrder(adj[here][0]); 

            visited[here] = 1; 
            cout << here << ' ';

            inOrder(adj[here][1]);
        }else{
            visited[here] = 1; 
            cout << here << ' '; 
        }
    }

} 
int main(){
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[2].push_back(5); 
    int root = 1;
    cout << "\n 트리순회 : postOrder \n";
    postOrder(root); memset(visited, 0, sizeof(visited));
    cout << "\n 트리순회 : preOrder \n"; 
    preOrder(root); memset(visited, 0, sizeof(visited)); 
    cout << "\n 트리순회 : inOrder \n"; 
    inOrder(root); 
    return 0;
}
/*
 트리순회 : postOrder
4 5 2 3 1
 트리순회 : preOrder
1 2 4 5 3
 트리순회 : inOrder
4 2 5 1 3
*/

읽어보슈 ㅎ

[SHEWANTSME]

Segment TREE

update함수

1.

void update(int node, int start, int end, int idx,int diff) {
    // arr[5] = 100으로 바꾸고싶어요! idx = 5 diff = 100
    int mid = (start + end) / 2;
    if (start == end) {
        tree[node] += diff; 
        return;
    }       
    if (idx > mid) {
        tree[node] += diff;
        update(node * 2 + 1, mid + 1, end, idx, diff);
    }
    if (idx <= mid) {
        tree[node] += diff;
        update(node * 2, start, mid, idx, diff);
    }
}

위처럼 하는게 나는 편함

void update(vector<long long> &tree, int node, int start, int end, int index, long long diff) {
    if (index < start || index > end) return;
    tree[node] = tree[node] + diff;
    if (start != end) {
        update(tree,node*2, start, (start+end)/2, index, diff);
        update(tree,node*2+1, (start+end)/2+1, end, index, diff);
    }
}

이렇게 해도 되고,,

// segment tree 
#include<iostream>
#include<vector>
#define ll long long 
#define endl "\n"
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
ll n, m, k;
ll arr[1000001];
ll tree[4000004]; // 4를 곱하면 모든 범위 커버 가능! 갯수에 대해서 2의 제곱형태를 가지기 때문임.

ll init(ll node, ll start, ll end) { // tree를 만드는 함수 
    // 반환값 있는 자료형으로 하는게 편함
    if (start == end)return tree[node] = arr[start]; // 리프노드는 트리노드가 arr[start]
    else {
        ll mid = (start + end) / 2;
        return tree[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
    } // 아닌애들은 그냥 이렇게 하면 됨 반쪼개서 재귀적으로
}
void update(ll node, ll start, ll end, ll idx, ll diff) {
        // arr[5] = 100으로 바꾸고싶어요! idx = 5 diff = 100 -> diff를 미리 바꿔놔야겠징?
    ll mid = (start + end) / 2; 
    if (start == end) { // 리프노드
        tree[node] += diff;  
        return; // 리프노드일때는 diff로 바꾸고 종료
    }       
    if (idx > mid) { // RC로 가는 놈
        tree[node] += diff;
        update(node * 2 + 1, mid + 1, end, idx, diff);
    }
    if (idx <= mid) { // LC로 가는놈
        tree[node] += diff;
        update(node * 2, start, mid, idx, diff);
    }
}
ll sum(ll node, ll start, ll end, ll left, ll right) {
    // left , right의 구간에 따라 반환값 달라짐
    if (left > end or right < start) return 0; // 애초에 겹치는거 없음 -> 리턴0
    if (left <= start and end <= right)return tree[node]; // 리프노드처럼 
    //start ,end를 left,right이 완전포개고 있으면 그냥 tree[node] 리턴하면됨 ( 그려보면 정확히 알 수 있음)
    ll mid = (start + end) / 2;
    // 나머지 애들은 반띵해서 더해주면됨 ( sum 함수니까)
    return sum(node * 2, start, mid, left, right) + sum(node * 2 + 1, mid + 1, end, left, right);
}

int main() {
    fastio;
    cin >> n >> m >> k;
    for (ll i = 0; i < n; i++) {
        cin >> arr[i];
    }
    init(1, 0, n-1);
    for (ll i = 0; i < m + k; i++) {
        ll a, b, c;
        cin >> a;
        if (a == 1) {
            cin >> b >> c;
            ll diff = c - arr[--b]; // 이건 그냥 
 // 원래 arr에서 b번째 원소값을 뺀다음에 새로운값 c를 더해줘야 그게 diff가 되어서 update를 수행할수있겟징
            arr[b] =c; // 이걸 안하면 update를 여러번할때, 처음 cin으로 받은 arr의 값이 갱신이 안되어서
            // 트리가 엉망이될수있음.(update한번만하면 상관없음)
            update(1, 0, n - 1, b, diff);
            //update b번째수 to c
        }
        if (a == 2) {
            cin>>b>>c;
            cout << sum(1, 0, n - 1, b-1, c-1) << endl;
            // 출력 b번째 수 부터 c번째 수
        }
    }
    return 0;
}

/*
 *** - 원래값 + c = diff ***

아 그리고 update함수를 ll으로 하면

ll update(int node, int l, int r, int idx, int v){
if(idx < l || r < idx) return tree[node]; 
if(l==r) return tree[node] = v; 
return tree[node] = update(node*2, l, (l+r)/2, idx, v) + update(node*2+1, (l+r)/2+1, r, idx, v); 
}
이렇게 해도 됨 ㅎ

void update(vector<long long> &tree, int node, int start, int end, int index, long long diff) {
    if (index < start || index > end) return;
    tree[node] = tree[node] + diff;
    if (start != end) {
        update(tree,node*2, start, (start+end)/2, index, diff);
        update(tree,node*2+1, (start+end)/2+1, end, index, diff);
    }
}
이렇게 해도 되고

*/

links

1. fenwick : https://www.acmicpc.net/blog/view/21
2. segment : https://www.acmicpc.net/blog/view/9
3. Lazy propagation : https://www.acmicpc.net/blog/view/26
4. segment(na dong bin) : https://m.blog.naver.com/ndb796/221282210534
5. barkingdog segment : file:///C:/Users/qhdms/Downloads/Binary%20Indexed%20Tree%20%20%20Segment%20Tree_blog.pdf
6. bowbowbow lazy : https://bowbowbow.tistory.com/4

[SHEWANTSME]

다익스트라..

// 다익스트라!
#include<iostream>
#include<queue>
#include<algorithm>
#define INF 1e9+11
#define PP pair<int,int>
using namespace std;
int v, e, start;
// {비용, 정점번호}
vector<pair<int, int>>adj[20005];
int d[20005];
int main() {
    cin >> v >> e >> start;
    fill(d, d + v + 1, INF);
    while (e--) {
        // u에서 v로 가는 가중치 w 인 간선 존재
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({ w,v });
    }
    //greater가 붙었으니 minheap이고(그래야 top이 min), pair가 각각
    // 들어간 pq ({거리 , 정점})

    priority_queue < PP, vector<PP>, greater<PP>>pq;
    //priority_queue<int, vector<int>,greater<int>>ppq;
    // 위에써놓은 ppq는 pq.push(4); 이렇게 하나의 원소만가능
    // pair로 넣고 싶어서 int 부분을 PP로 바꾼것일뿐
    d[start] = 0;
    pq.push({ d[start] , start });  
    while (not pq.empty()) {    
        // pq에서 거리가 가장작은원소 pick 
        auto cur = pq.top(); pq.pop();
       // 해당 거리가 최단거리 table에 있는 값과 다르면 넘어감
        if (d[cur.second] != cur.first) continue;
        // 해당원소에서 가리키는정점 : adj[cur.second]을 for돈다
        for (auto &e : adj[cur.second]) {
            //해당원소에서 가리키는 정점을 가리키는 값(e.first) +
            // 해당원소에서 가리키는 정점 (d[cur.second]_
            // 이 갱신이 되는지 안되는지 여부 판단.
            if (d[e.second] <= d[cur.second] + e.first) continue;
            //갱신되면
            d[e.second] = d[cur.second] + e.first;
            // pq에 삽입
            pq.push({ d[e.second] , e.second });
        }
    }
    // 그니까 맨첨 예시에서 d가
    // 0 ,inf, inf,inf,inf,inf 에서
    // 0, 3,2,5,inf ,inf 까지 되자나
    // 왜 되는거냐면 d[1]+2, d[1]+3, d[1]+5 가 현재 d[3], d[2], d[5]보다(inf) 작아서
    // 갱신이 되고 pq에 삽입이 되는거라서 그럼

    for (auto &e : d) {
        if (e == INF) cout << "INF" << endl;
        else cout << e << endl;
    }

    return 0;
}

헷갈리니깐 예시랑 같이 보도록!