Help Needed with CPP

I want to pass a function to another function, as a default parameter. The passed function takes two arguments as parameters and returns the result of a mathematical operation (could be one of +, -, /, *, min, max, gcd, lcm). Unfortunately, it throws std::bad_function_call error. I can give more details if needed. I am pasting the code here, it may help you realise what I actually need help with or to find exactly where the error occurs.

CPP Code
long sum(long a, long b) {
    return a + b;
}
class SegmentTree {
    private:
    ll default_value;
    vector<ll> tree;
    vector<ll> carry;
    int length;
    function<long(long, long)> key;
    public:
    SegmentTree(vector<int> a, int def_value = 0, function<long(long, long)> function = &sum) {
        default_value = def_value;
        vector<int> arr(a.begin(), a.end());
        int n = arr.size();
        while ((n & (n - 1)) != 0) {
            n++;
            arr.push_back(default_value);
        }
        tree.resize(2 * n, default_value);
        for(int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
        for(int i = n - 1; i > 0; i--) {
            tree[i] = key(tree[2 * i], tree[2 * i + 1]);
        }
        length = ((int)(tree.size())) / 2;
    }
    int size() {
        return length;
    }
}

@ssjgz @cubefreak777

PS: I am newbie to CPP. Please do explain bit more detailedly if possible.

Edit:
I somehow resolved the issue, but would love to hear from you any alternative that is more optimal in terms of memory and time.

The Working Code
function<ll(ll, ll)> sum = [](ll a, ll b) {return a + b;};

class SegmentTree {
    private:
    ll default_value;
    vector<ll> tree;
    vector<ll> carry;
    int length;
    function<long(long, long)> key;
    public:
    SegmentTree(vector<int> a, int def_value = 0, function<ll(ll, ll)> function = sum) {
        default_value = def_value;
        key = function;
        vector<int> arr(a.begin(), a.end());
        int n = arr.size();
        while ((n & (n - 1)) != 0) {
            n++;
            arr.push_back(default_value);
        }
        tree.resize(2 * n, default_value);
        for(int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
        for(int i = n - 1; i > 0; i--) {
            tree[i] = key(tree[2 * i], tree[2 * i + 1]);
        }
        length = ((int)(tree.size())) / 2;
        carry.resize(2 * n, default_value);
    }
}
1 Like

You’re not setting key to function.

Edit:

Too late XD

Edit2:

There was a big warning here that exposed the issue:

suman_18733097-blah.cpp:20:90: warning: unused parameter ‘function’ [-Wunused-parameter]
     SegmentTree(vector<int> a, int def_value = 0, function<long(long, long)> function = &sum) {

2 Likes

Yeah, just found that after an hour of debugging :sweat_smile:

Not at all a problem, but what I am doing - is that recommended or there are better ways to achieve the same.

1 Like

One more, how do I put the sum function inside the Class.
It shows the following message on putting the function inside the class.

a member with an in-class initializer must be const

Please post full code :slight_smile:

I am sorry for being late. Here’s the full code.

CPP Code
#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

function<ll(ll, ll)> sum = [](const ll a, const ll b) {return a + b;};

class SegmentTree {
    private:
    ll default_value;
    vector<ll> tree;
    vector<ll> carry;
    int length;
    function<long(long, long)> key;
    public:
    SegmentTree(vector<int> a, int def_value = 0, function<ll(ll, ll)> function = sum) {
        default_value = def_value;
        key = function;
        vector<int> arr(a.begin(), a.end());
        int n = arr.size();
        while ((n & (n - 1)) != 0) {
            n++;
            arr.push_back(default_value);
        }
        tree.resize(2 * n, default_value);
        for(int i = 0; i < n; i++) {
            tree[n + i] = arr[i];
        }
        for(int i = n - 1; i > 0; i--) {
            tree[i] = key(tree[2 * i], tree[2 * i + 1]);
        }
        length = ((int)(tree.size())) / 2;
        carry.resize(2 * n, default_value);
    }
    int size() {
        return length;
    }
    void pointUpdate(int index, long value) {
        pointUpdate(1, 0, length - 1, index, value);
    }
    private:
    long pointUpdate(int node, int node_lb, int node_ub, int index, long value) {
        if(index < node_lb || node_ub < index) {
            return tree[node];
        }
        else if(node_lb == node_ub && node_ub == index) {
            tree[node] = value;
        }
        else {
            long leftReturned = pointUpdate(2 * node, node_lb, (node_lb + node_ub) / 2, index, value);
            long rightReturned = pointUpdate(2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, index, value);
            tree[node] = key(leftReturned, rightReturned);
        }
        return tree[node];
    }
    public:
    void rangeUpdate(int range_lb, int range_ub, long value) {
        rangeUpdate(1, 0, length - 1, range_lb, range_ub, value);
    }
    private:
    long rangeUpdate(int node, int node_lb, int node_ub, int range_lb, int range_ub, long value) {
        if(range_lb <= node_lb && node_ub <= range_ub) {
            carry[node] = key(carry[node], value);
        }
        else if(node_ub < range_lb || range_ub < node_lb) {
            return carry[node];
        }
        else {
            rangeUpdate(2 * node, node_lb, (node_lb + node_ub) / 2, range_lb, range_ub, value);
            rangeUpdate(2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, range_lb, range_ub, value);
        }
        return carry[node];
    }
    public:
    long rangeQuery(int query_lb, int query_ub) {
        return rangeQuery(1, 0, length - 1, query_lb, query_ub);
    }
    private:
    long rangeQuery(int node, int node_lb, int node_ub, int query_lb, int query_ub) {
        if(query_lb <= node_lb && node_ub <= query_ub) {
            return key(tree[node], carry[node]);
        }
        else if(query_ub < node_lb || node_ub < query_lb) {
            return default_value;
        }
        else {
            long leftReturned = rangeQuery(2 * node, node_lb, (node_lb + node_ub) / 2, query_lb, query_ub);
            long rightReturned = rangeQuery(2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, query_lb, query_ub);
            return key(leftReturned, rightReturned);
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    SegmentTree tree = SegmentTree(a);
    for(int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if(type == 1) {
            int index, value;
            cin >> index >> value;
            tree.pointUpdate(index - 1, value);
        }
        else {
            int lb, ub;
            cin >> lb >> ub;
            cout << tree.rangeQuery(lb - 1, ub - 1) << '\n';
        }
    }
    return 0;
}

I want to put the function sum inside the SegmentTree Class. I tried making it static, but it didn’t work.

No problem; with a modern enough compiler (with decent C++17 support), the following should work:

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;


class SegmentTree {
    private:
        ll default_value;
        vector<ll> tree;
        vector<ll> carry;
        int length;
        inline static function<ll(ll, ll)> sum = [](const ll a, const ll b) {return a + b;};
        function<long(long, long)> key;
    public:
        SegmentTree(vector<int> a, int def_value = 0, function<ll(ll, ll)> function = sum) {
            default_value = def_value;
            key = function;
            vector<int> arr(a.begin(), a.end());
            int n = arr.size();
            while ((n & (n - 1)) != 0) {
                n++;
                arr.push_back(default_value);
            }
            tree.resize(2 * n, default_value);
            for(int i = 0; i < n; i++) {
                tree[n + i] = arr[i];
            }
            for(int i = n - 1; i > 0; i--) {
                tree[i] = key(tree[2 * i], tree[2 * i + 1]);
            }
            length = ((int)(tree.size())) / 2;
            carry.resize(2 * n, default_value);
        }
        int size() {
            return length;
        }
        void pointUpdate(int index, long value) {
            pointUpdate(1, 0, length - 1, index, value);
        }
    private:
        long pointUpdate(int node, int node_lb, int node_ub, int index, long value) {
            if(index < node_lb || node_ub < index) {
                return tree[node];
            }
            else if(node_lb == node_ub && node_ub == index) {
                tree[node] = value;
            }
            else {
                long leftReturned = pointUpdate(2 * node, node_lb, (node_lb + node_ub) / 2, index, value);
                long rightReturned = pointUpdate(2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, index, value);
                tree[node] = key(leftReturned, rightReturned);
            }
            return tree[node];
        }
    public:
        void rangeUpdate(int range_lb, int range_ub, long value) {
            rangeUpdate(1, 0, length - 1, range_lb, range_ub, value);
        }
    private:
        long rangeUpdate(int node, int node_lb, int node_ub, int range_lb, int range_ub, long value) {
            if(range_lb <= node_lb && node_ub <= range_ub) {
                carry[node] = key(carry[node], value);
            }
            else if(node_ub < range_lb || range_ub < node_lb) {
                return carry[node];
            }
            else {
                rangeUpdate(2 * node, node_lb, (node_lb + node_ub) / 2, range_lb, range_ub, value);
                rangeUpdate(2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, range_lb, range_ub, value);
            }
            return carry[node];
        }
    public:
        long rangeQuery(int query_lb, int query_ub) {
            return rangeQuery(1, 0, length - 1, query_lb, query_ub);
        }
    private:
        long rangeQuery(int node, int node_lb, int node_ub, int query_lb, int query_ub) {
            if(query_lb <= node_lb && node_ub <= query_ub) {
                return key(tree[node], carry[node]);
            }
            else if(query_ub < node_lb || node_ub < query_lb) {
                return default_value;
            }
            else {
                long leftReturned = rangeQuery(2 * node, node_lb, (node_lb + node_ub) / 2, query_lb, query_ub);
                long rightReturned = rangeQuery(2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, query_lb, query_ub);
                return key(leftReturned, rightReturned);
            }
        }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    SegmentTree tree = SegmentTree(a);
    for(int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if(type == 1) {
            int index, value;
            cin >> index >> value;
            tree.pointUpdate(index - 1, value);
        }
        else {
            int lb, ub;
            cin >> lb >> ub;
            cout << tree.rangeQuery(lb - 1, ub - 1) << '\n';
        }
    }
    return 0;
}
1 Like

writing a general segment tree i see. I Once wrote a multipurpose segment tree which accepts a func(this is used to combine 2 child nodes). Though i wrote it in python. In c++ there are ways to pass a function a parameter using pointers. Search on google (passing function as parameters). This should work

or maybe use Function pointer as argument in C - javatpoint. cause he is writing a multipurpose segment tree. He wants to change sum to . min or max, or xor, depending on what kind of segment tree he wants. This is dope as u can simply change function for a different type of segment tree. I did it once too :stuck_out_tongue:

1 Like

Hey, thanks a lot for this.

1 Like