Click here to Skip to main content
15,914,225 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
C++
#include <iostream>
#include <vector>
using namespace std;

long long seg[4*1000000];
vector<long long> vettore;
void update(int ind, int low, int high, int l,int differenza){
 if(high<l || low>l)return;
   seg[ind]+=differenza;
   int mid=(low+high)/2;
   update(2*ind+1,low,mid,l,differenza);
   update(2*ind+2,mid+1,high,l,differenza);//if i erase this function it runs
  }
 void build(int ind, int low, int high){
  if(low==high){
     seg[ind]=vettore[low];
     return;
  }
  int mid=(low+high)/2;
  build(2*ind+1,low,mid);
  build(2*ind+2,mid+1,high);
  seg[ind]=seg[2*ind+1]+seg[2*ind+2];
 }
 void init(vector<long long> a) {
 vettore.resize(a.size());
 for(int i=0;i<a.size();i++)vettore[i]=a[i];
  build(0,0,a.size()-1);
 }


long long query(int ind, int low, int high, int l, int r){
if(low>=l&&high<=r){
   return seg[ind];
}
if(high<l || low>r)return 0;
 int mid=(low+high)/2;
 long long left=query(2*ind+1,low,mid,l,r);
 long long right=query(2*ind+2,mid+1,high,l,r);
 return left+right;
 }


long long get_sum(int l, int r) {
r--;
return query(0,0,vettore.size()-1,l,r);
}
/*
void add(int l, int r, long long x) {
for(int i=l;i<r;i++)vettore[i]+=x;
}
*/
 void set_range(int l, int r, long long x) {
for(int i=l;i<r;i++){
   int differenza=x-vettore[i];
   update(0,0,vettore.size()-1,i,differenza);
  vettore[i]=x;
 }
 }
/*
long long get_min(int l, int r) {
long long min=vettore[l];
l++;
 for(int i=l;i<r;i++){
   if(vettore[i]<min)min=vettore[i];
 }
 return min;
 }

 int lower_bound(int l, int r, long long x) {
  for(int i=l;i<r;i++){
   if(vettore[i]<x)return i;
 }
 return -1;
 }
 */
 int main(){
  ios::sync_with_stdio(false);


int n, q;
cin >> n >> q;

vector<long long> a(n);
for (int i = 0; i < n; i++)
    cin >> a[i];
init(a);
for (int i = 0; i < q; i++) {
    int op, l, r;
    long long x;
    cin >> op;
cin >> l >> r;
    if (op == 2 or op == 3 or op == 5)
        cin >> x;
    if (op == 1) cout << get_sum(l, r) << "\n";
    if (op == 2) add(l, r, x);
    if (op == 3) set_range(l, r, x);
    if (op == 4) cout << get_min(l, r) << "\n";
    if (op == 5) cout << lower_bound(l, r, x) << "\n";
}

return 0;
}


What I have tried:

The commented functions have to be implemented, but that isn't the point. Can you help me fixing the error? I'm trying to implementing a segment tree, but I know I have to study. I searched the error code online, i know what is, but I don't know how to fix it. If i debug my code, it says segmentation fault but I don't know how it is possible. Can you help me with my error?
Posted
Updated 16-May-22 12:52pm
v3

It's called a "segmentation fault" - it occurs when you try to access memory which is not yours, either t5hrough a bad pointer, or through an invalid array index.

Use the debugger to find out the value of ind and the size of seg then think about why it got that big! (But since l doesn't change but ind does, and the only way out of that is on a high / low comparison I suspect you logic is ... incorrect.

But since I have no idea what that code is meant to do, I can't comment on fixing the problem!
 
Share this answer
 
Comments
Francesco Famosi 15-May-22 12:49pm    
thanks, but how can i find out the value of ind with the debugger?
OriginalGriff 15-May-22 13:27pm    
Google for the name of your IDE and "Debugger" - you'll find the instructions there.
With this program, the user has to make various entries that are never displayed on the screen.
A test with the following inputs will crash because a vector is too small and the index does not exist.
2 3  // n and q 
100  // a[0] 
200  // a[1]
3    // op
4    // l
5    // r
6    // x 


C++
if (op == 3) set_range(l, r, x);

C++
void set_range(int l, int r, long long x) {
  for (int i = l; i<r; i++) {
    int differenza = x - vettore[i];  // <-- crash because index does not exist
    update(0, 0, vettore.size() - 1, i, differenza);
    vettore[i] = x;
  }
}

The entries are neither explained nor checked, which inevitably leads to problems.
There are several recursive functions that can also cause problems with arbitrary input.
The inputs should be explained, displayed and checked.
Which inputs lead to the crash in the question is not shown.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900