fork download

copy

// lazy part is pending -> other code is fine
class SGtree
{
    vi seg, lazy;
 
public:
    SGtree(int n)
    {
        // Adjust deafault value (if needed) --> size = [4*arr.size()]
        seg.resize(4 * n + 1, 0);
        lazy.resize(4 * n + 1, 0);
    }
 
    void build(vi &arr, int l, int r, int ind)
    {
        if (l == r)
        {
            // Change accordingly (for single element)
            seg[ind] = arr[l];
            return;
        }
 
        int mid = (l + r) / 2;
        build(arr, l, mid, 2 * ind + 1);
        build(arr, mid + 1, r, 2 * ind + 2);
 
        // Assuming operation is sum of range[l, r]
        seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
    }
 
    // query on [l, r] where l and r are fixed
    int tell(int l, int r, int a, int b, int ind)
    {
        // Adjust deafault value of lazy (if needed)
        if (lazy[ind])
        {
            if (a != b)
            {
                // if (a!=b) -> not leaf -> have childs
                lazy[2 * ind + 1] = lazy[ind];
                lazy[2 * ind + 2] = lazy[ind];
            }
 
            // Assuming operation is sum of range[l, r]
            // Update accordingly -> added val (b-a+1) times {bcz sum query on index[a...b]}
            seg[ind] += lazy[ind] * (b - a + 1);
 
            lazy[ind] = 0; // Adjust deafault value of lazy (if needed)
        }
 
        if (l <= a && b <= r)
        {
            return seg[ind];
        }
 
        if (r < a || b < l) // NO overlap
        {
            // Return the default value
            return 0;
        }
 
        int mid = (a + b) / 2;
        int x = tell(l, r, a, mid, 2 * ind + 1);
        int y = tell(l, r, mid + 1, b, 2 * ind + 2);
 
        // Do the operation
        return x + y;
    }
 
    // point update of arr[x] = val
    void update(int l, int r, int ind, int x, int val)
    {
        if (l == r)
        {
            seg[ind] = val;
            return;
        }
 
        int mid = (l + r) / 2;
        if (x <= mid)
        {
            update(l, mid, 2 * ind + 1, x, val);
        }
        else
        {
            update(mid + 1, r, 2 * ind + 2, x, val);
        }
 
        // Assuming operation is sum of range[l, r]
        seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
    }
 
    // range update from {arr[l].....arr[r]} to val
    void lazyPropagation(int l, int r, int a, int b, int ind, int val)
    {
        if (l <= a && b <= r)
        {
            // If 2 consecutive updates on same node
            lazy[ind] += val;
            cout << lazy[ind] << " " << ind << " " << a << " " << b << endl;
            return;
        }
 
        if (r < a || b < l) // NO overlap
        {
            return;
        }
 
        int mid = (a + b) / 2;
        lazyPropagation(l, r, a, mid, 2 * ind + 1, val);
        lazyPropagation(l, r, mid + 1, b, 2 * ind + 2, val);
    }
};
 

prog.cpp:4:5: error: ‘vi’ does not name a type; did you mean ‘void’?
     vi seg, lazy;
     ^~
     void
prog.cpp:14:16: error: ‘vi’ has not been declared
     void build(vi &arr, int l, int r, int ind)
                ^~
prog.cpp: In constructor ‘SGtree::SGtree(int)’:
prog.cpp:10:9: error: ‘seg’ was not declared in this scope
         seg.resize(4 * n + 1, 0);
         ^~~
prog.cpp:11:9: error: ‘lazy’ was not declared in this scope
         lazy.resize(4 * n + 1, 0);
         ^~~~
prog.cpp: In member function ‘void SGtree::build(int&, int, int, int)’:
prog.cpp:19:13: error: ‘seg’ was not declared in this scope
             seg[ind] = arr[l];
             ^~~
prog.cpp:19:29: error: invalid types ‘int[int]’ for array subscript
             seg[ind] = arr[l];
                             ^
prog.cpp:28:9: error: ‘seg’ was not declared in this scope
         seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
         ^~~
prog.cpp: In member function ‘int SGtree::tell(int, int, int, int, int)’:
prog.cpp:35:13: error: ‘lazy’ was not declared in this scope
         if (lazy[ind])
             ^~~~
prog.cpp:46:13: error: ‘seg’ was not declared in this scope
             seg[ind] += lazy[ind] * (b - a + 1);
             ^~~
prog.cpp:53:20: error: ‘seg’ was not declared in this scope
             return seg[ind];
                    ^~~
prog.cpp: In member function ‘void SGtree::update(int, int, int, int, int)’:
prog.cpp:75:13: error: ‘seg’ was not declared in this scope
             seg[ind] = val;
             ^~~
prog.cpp:90:9: error: ‘seg’ was not declared in this scope
         seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
         ^~~
prog.cpp: In member function ‘void SGtree::lazyPropagation(int, int, int, int, int, int)’:
prog.cpp:99:13: error: ‘lazy’ was not declared in this scope
             lazy[ind] += val;
             ^~~~
prog.cpp:100:13: error: ‘cout’ was not declared in this scope
             cout << lazy[ind] << " " << ind << " " << a << " " << b << endl;
             ^~~~
prog.cpp:100:72: error: ‘endl’ was not declared in this scope
             cout << lazy[ind] << " " << ind << " " << a << " " << b << endl;
                                                                        ^~~~
prog.cpp:100:72: note: suggested alternative: ‘ind’
             cout << lazy[ind] << " " << ind << " " << a << " " << b << endl;
                                                                        ^~~~
                                                                        ind

Standard output is empty