iamdumb's blog

Help needed with first segment tree problem.
By iamdumb, history, 9 years ago, In English

Hello everyone,I have just learnt segment tree(range sum and range min/max).I tried first segment tree question which is this.But I am getting what value should I assign to the parents while building the tree.I know What to assign to leaf nodes but not getting to the parent.Here I am facing problem

void build(string &s,int pos,int low,int high)
{
    if(low==high)
    {
        tree[pos]=s[low]-'0';
        return;
    }
    int mid=(low+high)/2;
    build(s,2*pos,low,mid);
    build(s,2*pos+1,mid+1,high);
    tree[pos]=                    //Here ?? What should be in this place
}
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

You have two options here, and since you have range updates and point queries, you don't need to put anything in the parent node.

Option 1: Update ranges and sum all the values from root to leaf. For the update, start at the root and go down. If at any time, the current range is outside the update range, return. If there's a partial intersection, recurse on the children. And if the range is fully contained, add 1 to it and return. For the query, you'd go down from the root to the desired leaf adding all the values you find along the way. If the final sum is odd, then the bit is inverted.

Option 2: Use prefix sums. This is the preferred option if you ask me, since it's easier and shorter to implement. Instead of using a segment tree, use a BIT and when you have to update range [l, r], instead of updating the range, add 1 to position l and subtract 1 from position r + 1. Then use prefix sums to find the value of any position. BIT is the perfect data structure for this, since the standard operations are point update and prefix sum query.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain what do you mean by " since you have range updates and point queries, you don't need to put anything in the parent node"

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Your queries are on points (i.e. left = right). This means you have to reach a leaf in order to get the final value, so you don't need to do any kind of lazy propagation or parent updating. Those kinds of things are only needed when you query ranges, so that you can return a value when you are in the proper node.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think using the segment tree to count how many time each position was inverted is enough. in that case initialize all nodes of the segment tree by 0. and when any range is inverted, just increase the value of the relevent node of segment tree by 1. and at the time of query just find the range sum.

→ Reply