Segmentation Tree

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

using namespace std;

void Build(int arr[], int segtree[], int s, int e, int index) {

    if (s == e) {
        segtree[index] = arr[s];

    }
    else {

        int mid = (s + e) / 2;

        Build(arr, segtree, s, mid, 2 * index);
        Build(arr, segtree, mid + 1, e, 2 * index + 1);
        if (segtree[2 * index] < segtree[2 * index + 1])
            segtree[index] = segtree[2 * index];
        else
            segtree[index] = segtree[2 * index + 1];
    }
}

void update(int node, int start,int end ,int idx,int val, int tree[],int a[]) {


    if (start == end)
    {
        a[idx] = val;
        tree[node] = val;
    }
    else
    {
        int mid = (start + end) / 2;
        if (idx >= start && idx <= mid)
            update(2 * node, start, mid, idx, val, tree, a);
        else
            update(2 * node + 1, mid + 1, end, idx, val, tree, a);

        if (tree[2 * node] < tree[2 * node + 1])
            tree[node] = tree[2 * node];
        else
            tree[node] = tree[2 * node + 1];
    }


}
int Query(int segtree[], int s, int e, int index, int left, int right) {

    //base case

    if (s > right or e < left)
    {
        return 100005;
    }

    if (s >= left && e <= right)
    {
        return segtree[index];
    }

    int mid = (s + e) / 2;
    int p1 = Query(segtree, s, mid, 2 * index, left, right);
    int p2 = Query(segtree, mid + 1, e, 2 * index + 1, left, right);
    if (p1 < p2)
        return p1;
    else
        return p2;
}



int main() {
    int s[2000005], v[100005];
    int n, q;
    cin >> n >> q;



    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        v[i] = x;
    }

    Build(v, s, 1, n, 1);

    while (q--) {
        int l, r;
        char ch;

        cin >> ch >> l >> r;

        //int Query(int *segtree, int s, int e, int index, int left, int right)
        if (ch == 'q') {
            int c = Query(s, 1, n, 1, l, r);
            cout << c << endl;
        }
        else
            update(1,1,n,l,r,s,v);

        //void update(int node, int start, int end, int idx, int val, int tree[], int a[])
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Aggressive cow

  #include<iostream> #include <vector> #include<string> #include<queue> #include<algorithm> #include <unordered_map>   using namespace std ; typedef long long int ll ;     bool possible ( vector < int > v, ll mid, ll k ) {   int last ; int cnt = 0 ; last = v [ 0 ] ; cnt ++ ; for ( int i = 1 ; i < v. size ( ) ; i ++ ) { if ( v [ i ] - last >= mid ) { cnt ++ ; last = v [ i ] ;   if ( cnt == k ) return true ; } }   if ( cnt >= k ) return true ; else return false ;         }     int main ( ) {     int t ; cin >> t ; while ( t -- ) {   int n, k ; cin >> n >> k ;   vector < int > v ( n, 0 ) ;   for ( int i = 0 ; i < n ; i ++ ) cin >> v [ i ] ;   sort ( v. begin ( ) , v. end ( ) ) ;   long long int resul...
Read more

LRU Cache Implementation

 // LRU Cache implementation #include <iostream> #include <unordered_map> using namespace std; class DLLNode { public: int key; int value; DLLNode *next; DLLNode *prev; DLLNode(int k, int v) { this->key = k; this->prev = NULL; this->value = v; this->next = NULL; } }; //Data structure and globals unordered_map<int, DLLNode*> cache; int Size =0; int capacity; DLLNode * head = new DLLNode(-1, -1); DLLNode * tail = new DLLNode(-1, -1); void addNodeAtHead(DLLNode *node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; return; } void removeNode(DLLNode* node) { DLLNode* prev = node->prev; DLLNode* next = node->next; prev->next = next; next->prev = prev; } int removeFromTail() { DLLNode* temp = tail->prev; removeNode(temp); return temp->key; } void moveToHead(DLLNode *node) { cout << "access this key" << node->key...
Read more