c++segment-treefenwick-treebinary-indexed-tree

String query with binary indexed tree


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);
        }

    }

Solution

  • 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.