String query with binary indexed tree

Question

I want to range query a string using Fenwick tree. But something is going wrong with my code. Concatenation is giving error Eror is:[Error] no match for 'operator+=' (operand types are 'std::vector >' and 'std::string {aka std::basic_string}') Given a string s, I want to store the string in this fenwick tree. e.g. s=abcdef, on BIT it should like(top-bottom) a ab-c abcd-e abcd-ef Tree Structure

vector<string> BIT[100005];
    int n;
    void BI(int x,string c)
    {
        for(;x<=n;x+=x&-x)  
        {
            BIT[x]+=c;
        }

    }

    int main()
    {
        cin>>n;
        string s;
        for(int i=1;i<=n;i++)
        {   cin>>s;
            BI(i,s);
        }

    }

It's not clear what data this is processing, nor what the output should be. — tadman
– tadman, Commented Jul 10, 2017 at 14:27
e.g. s=abcdef, on BIT it should like(up-bottom) a ab-c abcd-e abcd-ef — nRT
– nRT, Commented Jul 10, 2017 at 14:28
Isn't std::vector<x> y[n] a C-style array of vectors? Why not a std::vector<std::vector<std::string>>? — tadman
– tadman, Commented Jul 10, 2017 at 14:28
Don't understand your tree formatting. You mean "top to bottom," right? But what are the spaces and what are the dashes? Can you write in heap format, e.g. a, ab, c, abcd, null, null, e, etc. — Andrew Cheong
– Andrew Cheong, Commented Jul 10, 2017 at 14:35
spaces is between two consecutive depths and dashes meant parent-child — nRT
– nRT, Commented Jul 10, 2017 at 14:38

Andrew Cheong · Accepted Answer · 2017-07-10 14:50:49Z

1

This

vector<string> BIT[100005];

and this

BIT[x]+=c;

don't go together. You have an array of vectors of strings (2-dimensional matrix, basically). And you are trying to add string c to a vector at BIT[x]. Your compile errors should be telling you this.

You probably did not mean to make an array of vector of strings. To make a vector of strings with size 100005, do this:

vector<string> BIT(100005);

i.e. parentheses, not square brackets.

answered Jul 10, 2017 at 14:50

Andrew Cheong

30.4k17 gold badges103 silver badges173 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

String query with binary indexed tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related