aajjbb's blog

By aajjbb, 5 years ago, In English,

Hello, I'm a pretty beginner with segment trees and I'm in doubt on this problem, I can build the tree but the queries for look for the right interval with the biggest sum is wrong, can someone point out what is wrong with my method func. Thanks in advance.

Problem Statement

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <utility>
#include <functional>
#include <valarray>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>

using namespace std;

#define REP(i, n) for(i = 0; i < (n); i++)
#define FOR(i, a, n) for(i = a; i < n; i++)
#define REV(i, a, n) for(i = a; i > n; i--)

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

typedef long long ll;
typedef long double ld;

#define MAXN 5000010
#define INF 1000001000

int n, a[MAXN], t[4*MAXN];
int b, c, i, m, tmp, x;

void build (int a[], int v, int tl, int tr) {
    if (tl == tr)
        t[v] = a[tl];
    else {
        int tm = (tl + tr) / 2;
        build (a, v*2, tl, tm);
        build (a, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

int func(int v, int tl, int tr, int l, int r) {
    if(l > tr || r < tl) {
        return -INF;
    }
    if(tl >= l && tr <= r) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    int p1 = func(2 * v, tl, (tl + tr) / 2, l, r);
    int p2 = func(2 * v + 1, ((tl + tr) / 2) + 1, tr, l, r);

    if(p1 > p2) return p1;
    else return p2;
}
int main(void) {
    freopen("i.in", "r", stdin);
    scanf("%d", &x);
    REP(i, x) {
        scanf("%d", &a[i+1]);
    }
    build(a, 1, 1, x+1);    
    scanf("%d", &m);
    REP(i, m) {
        scanf("%d%d", &b, &c);
        printf("%d\n", func(1, 1, x+1, b, c));
    }
    return 0;
}


 
 
 
 

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

As I understand, in func you are returning p1 or p2, but result may be the intersection of them.
Hint in spoiler.

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

    but how would I return the intersect of them ? I think this method looks in all intervals between i and j, and I try to get the bigger of them, what would I change to implement your Idea ? also, what do you mean with 'Hint in spoiler' ?

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

      See iTwin's rev.1 comment. I think it's the spoiler he meant.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For each segment [x..y] you need to know four integers:
1) SUM — sum of all numbers in this segment
2) BEST — maximal sum of any subsegment of this segment
3) BestLeft maximal sum of any subsegment [i..j] of this segment, and i == x
4) BestRight maximal sum of any subsegment [i..j] of this segment, and j == y
if we know all these integers for two intervals [L..M] and [M+1..R] we can easy calculate them for interval [L..R].

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

    This is my naive Idea for what you have explained ans it's wrong, I'm in doubt yet on how to get BestLeft and BestRight.

    int func(int v, int tl, int tr, int l, int r) {
        if(l > tr || r < tl) {
            return 0;
        }
        if(tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        int bestLeft = func(2 * v, tl, (tl + tr) / 2, l, r);
        int bestRight = func(2 * v + 1, ((tl + tr) / 2) + 1, tr, l, r);
        int sum = func(2 * v, tl, (tl + tr) / 2, l, r) + func(2 * v + 1, ((tl + tr) / 2) + 1, tr, l, r);
        best = max(best, max(bestLeft, max(bestRight, sum)));
    }
    
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell me why we need to calculate all these 4 different things...I am unable to get the logic out of this..help will be highly appreciated,,...

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks i got it...

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

        Thanks, finally I understand.

        :)

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        i cant understand something in your code. i also submitted your solution and it get WA ! it seems test cases improved.

        why you can gurantee bestRight(leftChild)+BestLeft(RightChild) enclose [x..y] interval ? for example we have interval [0 10] and query is interval [2..8] , how you can be ensure that BestRight[0..5] (left child of main interval) is not less than 2 ?

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

        Why using structure in the implementation

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          It's for 3 years ago bro...

          However according to your handle you are dumb :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

here you can get a nice tutorial about maximum sub-segment sum. http://e-maxx.ru/algo/segment_tree

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

    Thank you, it's solved, this article is really good, this is the final accepted code: Link

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if all numbers r negative ur program will print negative number,not sure but maybe u can take an empty segment so the answer will be 0.