Segment Tree – Live with passion

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

#define sz 1024001
#define INV 1
#define SET 2
#define RESET 3

using namespace std;

struct segment{
	int pending_op_typ;
	int sum;

	int left,right;
	int len;
};
segment tree[sz*4];
string ss;

void init(int node,int b,int e)
{
	tree[node].len = e-b+1;
	tree[node].left=b;
	tree[node].right=e;
	tree[node].pending_op_typ=0;
	if(b==e)
	{

		if(ss[b]=='1')
		tree[node].sum=1;
		else
		tree[node].sum=0;
		return;
	}
	int Left = node*2;
	int Right = (node<<1)|1;
	int mid = (b+e)>>1;
	init(Left,b,mid);
	init(Right,mid+1,e);
	tree[node].sum=tree[Left].sum+tree[Right].sum;
}

void change(int node,int opr)
{
	if(opr==SET)
	{
		tree[node].sum=tree[node].len;
		tree[node].pending_op_typ=opr;
	}
	else if(opr==RESET)
	{
		tree[node].sum=0;
		tree[node].pending_op_typ=opr;
	}
	else if(opr==INV)
	{
		tree[node].sum=tree[node].len-tree[node].sum;
		if(tree[node].pending_op_typ==SET)//inverse the operation and apply
		{
			tree[node].pending_op_typ=RESET;
		}
		else if(tree[node].pending_op_typ==RESET)//inverse the operation and apply
		{
			tree[node].pending_op_typ=SET;
		}
		else if(tree[node].pending_op_typ==INV)//inverse the operation and apply
		{
			tree[node].pending_op_typ=0;
		}
		else if(tree[node].pending_op_typ==0)//inverse the operation and apply
		{
			tree[node].pending_op_typ=INV;
		}
	}

}

void propagate(int node)
{
	if(tree[node].pending_op_typ==0)
	return;
	int Left=2*node;
	int Right=2*node+1;
	change(Left,tree[node].pending_op_typ);
	change(Right,tree[node].pending_op_typ);
	tree[node].pending_op_typ=0;
}

int query(int node,int i,int j)
{
	int b=tree[node].left;
	int e=tree[node].right;
	if(i>e || j<b)
	return 0;
	propagate(node);
	if(i<=b && j>=e)
	{
		return tree[node].sum;
	}
	else
	{
		int Left = node<<1;
		int Right = (node<<1)|1;
		int p1 = query(Left,i,j);
		int p2 = query(Right,i,j);
		return p1+p2;
	}
}


void update(int node,int i,int j,int opr)
{
	int left = tree[node].left,right=tree[node].right;
	propagate(node);
	if(i>right || j<left)
	return;
	if(left>=i && right<=j)
	{
		change(node,opr);
		return;
	}
	else
	{
		int Left = node*2;
		int Right = node*2+1;
		update(Left,i,j,opr);
		update(Right,i,j,opr);
		tree[node].sum=tree[Left].sum+tree[Right].sum;
	}
}
// 0 for Barbary, 1 for Buccaneer
int main()
{
	int t,tym,M,qry;
	int a,b;
	int kase=1,cnt;
	bool flag;
	string s,str;
	scanf("%d",&t);

	while(t--)
	{
		flag=0;
		cnt=1;
		scanf("%d",&tym);
		s="";
		while(tym--)
		{
			scanf("%d",&M);
			cin>>str;
			while(M--)
				s.append(str);
		}
		ss = "2";
		ss.append(s);
		init(1,1,ss.size()-1);//init(1,1,ss.size()-1);
		scanf("%d",&qry);
		while(qry--)
		{
			cin>>str;
			scanf("%d%d",&a,&b);
			if(str=="F")
			{
				update(1,a+1,b+1,SET);//convert to buccaneer
			}
			else if(str=="E")
			{
				update(1,a+1,b+1,RESET);//convert to barbary =0
			}
			else if(str=="I")
			{
				update(1,a+1,b+1,INV);//inverse the pirates
			}
			else if(str=="S")
			{
				if(flag==0)
				{
					cout<<"Case "<<kase++<<":\n";
				}
				flag=1;
				cout<<"Q"<<cnt++<<": ";
				cout<<query(1,a+1,b+1)<<"\n";
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#define sz 1024001

#define INV 1

#define SET 2

#define RESET 3

using namespace std;

struct segment{

int pending_op_typ;

int sum;

int left,right;

int len;

};

segment tree[sz*4];

string ss;

void init(int node,int b,int e)

{

tree[node].len = e-b+1;

tree[node].left=b;

tree[node].right=e;

tree[node].pending_op_typ=0;

if(b==e)

{

if(ss[b]=='1')

tree[node].sum=1;

else

tree[node].sum=0;

return;

}

int Left = node*2;

int Right = (node<<1)|1;

int mid = (b+e)>>1;

init(Left,b,mid);

init(Right,mid+1,e);

tree[node].sum=tree[Left].sum+tree[Right].sum;

}

void change(int node,int opr)

{

if(opr==SET)

{

tree[node].sum=tree[node].len;

tree[node].pending_op_typ=opr;

}

else if(opr==RESET)

{

tree[node].sum=0;

tree[node].pending_op_typ=opr;

}

else if(opr==INV)

{

tree[node].sum=tree[node].len-tree[node].sum;

if(tree[node].pending_op_typ==SET)//inverse the operation and apply

{

tree[node].pending_op_typ=RESET;

}

else if(tree[node].pending_op_typ==RESET)//inverse the operation and apply

{

tree[node].pending_op_typ=SET;

}

else if(tree[node].pending_op_typ==INV)//inverse the operation and apply

{

tree[node].pending_op_typ=0;

}

else if(tree[node].pending_op_typ==0)//inverse the operation and apply

{

tree[node].pending_op_typ=INV;

}

void propagate(int node)

{

if(tree[node].pending_op_typ==0)

return;

int Left=2*node;

int Right=2*node+1;

change(Left,tree[node].pending_op_typ);

change(Right,tree[node].pending_op_typ);

tree[node].pending_op_typ=0;

}

int query(int node,int i,int j)

{

int b=tree[node].left;

int e=tree[node].right;

if(i>e || j<b)

return 0;

propagate(node);

if(i<=b && j>=e)

{

return tree[node].sum;

}

else

{

int Left = node<<1;

int Right = (node<<1)|1;

int p1 = query(Left,i,j);

int p2 = query(Right,i,j);

return p1+p2;

}

void update(int node,int i,int j,int opr)

{

int left = tree[node].left,right=tree[node].right;

propagate(node);

if(i>right || j<left)

return;

if(left>=i && right<=j)

{

change(node,opr);

return;

}

else

{

int Left = node*2;

int Right = node*2+1;

update(Left,i,j,opr);

update(Right,i,j,opr);

tree[node].sum=tree[Left].sum+tree[Right].sum;

}

// 0 for Barbary, 1 for Buccaneer

int main()

{

int t,tym,M,qry;

int a,b;

int kase=1,cnt;

bool flag;

string s,str;

scanf("%d",&t);

while(t--)

{

flag=0;

cnt=1;

scanf("%d",&tym);

s="";

while(tym--)

{

scanf("%d",&M);

cin>>str;

while(M--)

s.append(str);

}

ss = "2";

ss.append(s);

init(1,1,ss.size()-1);//init(1,1,ss.size()-1);

scanf("%d",&qry);

while(qry--)

{

cin>>str;

scanf("%d%d",&a,&b);

if(str=="F")

{

update(1,a+1,b+1,SET);//convert to buccaneer

}

else if(str=="E")

{

update(1,a+1,b+1,RESET);//convert to barbary =0

}

else if(str=="I")

{

update(1,a+1,b+1,INV);//inverse the pirates

}

else if(str=="S")

{

if(flag==0)

{

cout<<"Case "<<kase++<<":\n";

}

flag=1;

cout<<"Q"<<cnt++<<": ";

cout<<query(1,a+1,b+1)<<"\n";

}

return 0;

}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

#define ll long long
#define sz 250005

using namespace std;

struct segment{
	ll left,right;
	ll len;

	ll first_inc,last_inc;
	ll totalAB;

	bool isSetvalue;
	ll cary;
	ll sum;

};

segment arr[sz*4];


void changeAB(ll frist_incr,ll last_incr,int node,ll step)
{
	arr[node].totalAB += step;
	arr[node].first_inc += frist_incr;
	arr[node].last_inc += last_incr;
	arr[node].sum += ((frist_incr+last_incr)*arr[node].len)/2;
}

void changeC(int node,ll val)
{
	arr[node].sum = arr[node].len*val;
	arr[node].isSetvalue=1;
	arr[node].cary=val;

	arr[node].totalAB=0;
	arr[node].first_inc=0;
	arr[node].last_inc=0;
}

void propagate(int node)
{
	ll add1 = arr[node].first_inc;
	ll add2 = arr[node].last_inc;
	ll step = arr[node].totalAB;

	if(arr[node].isSetvalue)
	{
		ll Left=2*node;
		ll Right=2*node+1;
		changeC(Left,arr[node].cary);
		changeC(Right,arr[node].cary);
		arr[node].isSetvalue=0;
		arr[node].cary=0;
	}
	if(add1 || add2 || step)
	{
		ll Left=2*node;
		ll Right=2*node+1;
		ll mid=add1+step*(arr[Left].len-1);
		changeAB(add1,mid,Left,step);
		changeAB(mid+step,add2,Right,step);

		arr[node].first_inc=0;
		arr[node].last_inc=0;
		arr[node].totalAB=0;
	}

}

//update node for the range
void updateAB(int node,int i,int j,ll step)
{
	ll Left=arr[node].left,Right=arr[node].right,mid;
	ll first_inc,last_inc;
	if(i>Right || j<Left)
	{
		return;
	}
	if(i<=Left && j>=Right)
	{
		ll k = step;
		if(step>=0)
		{
			first_inc = (Left-i+1);
			last_inc  = (Right-i+1);
		}
		else
		{
			first_inc = (j-Left+1);
			last_inc  = (j-Right+1);
		}
		changeAB(first_inc,last_inc,node,k);
		return;
	}
	else
	{
		propagate(node);
		Left=2*node;
		Right=(node<<1) | 1;
		updateAB(Left, i, j,step);
		updateAB(Right, i, j,step);
		arr[node].sum = arr[Left].sum+arr[Right].sum;
		return;
	}
	return;
}

void updateC(int node,int i,int j,ll val)
{
	ll Left,Right,mid;
	ll b=arr[node].left;
	ll e=arr[node].right;
	if(i>e || j<b)
	return;
	else if(i<=b && j>=e)
	{
		arr[node].sum = (val*(e-b+1));
		arr[node].cary=val;
		arr[node].isSetvalue=1;

		arr[node].totalAB=0;
		arr[node].first_inc=0;
		arr[node].last_inc=0;
		return;
	}
	else
	{
		propagate(node);
		Left = 2*node;
		Right = Left+1;
		mid = (b+e)>>1;
		updateC(Left,i,j,val);
		updateC(Right,i,j,val);
		arr[node].sum = (arr[Left].sum+arr[Right].sum);
		return;
	}
	return;
}

ll query(int node,int i,int j)
{
	ll b = arr[node].left;
	ll e = arr[node].right;

	if(i>e || j<b)
	{
		return 0;
	}
	if(i<=b && j>=e)
	{
		return arr[node].sum;
	}
	propagate(node);
	ll Left = node<<1;
	ll Right = Left+1;

	ll p1 = query(Left, i, j);
	ll p2 = query(Right, i, j);
	return p1+p2;
}


void _init(int b,int e,int node)
{
	arr[node].sum=0; arr[node].len=e-b+1;
	arr[node].totalAB=0;
	arr[node].cary=0;
	arr[node].first_inc=0; arr[node].last_inc=0;
	arr[node].isSetvalue=0;
	arr[node].left=b;arr[node].right=e;
	if(b!=e)
	{
		int mid=(b+e)/2;
		_init(b,mid,node<<1);
		_init(mid+1,e,(node<<1)|1);
	}
}
int main()
{
	int t;
	string s;
	int start,end,val;

	while(scanf("%d",&t)!=EOF)
	{
		_init(1,sz-5,1);
		while(t--)
		{
			cin>>s;
			if(s[0]=='A')
			{
				cin>>start>>end;
				updateAB(1,start,end,1);//+1 increment increasing ascending order
			}
			else if(s[0]=='B')
			{
				cin>>start>>end;
				updateAB(1,start,end,-1);//-1 increment decreasing ascending order
			}
			else if(s[0]=='C')
			{
				cin>>start>>end>>val;
				updateC(1,start,end,val);
			}
			else if(s[0]=='S')
			{
				cin>>start>>end;
				cout<<query(1,start,end)<<"\n";
			}
		}
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <vector>

#define ll long long

#define sz 250005

using namespace std;

struct segment{

ll left,right;

ll len;

ll first_inc,last_inc;

ll totalAB;

bool isSetvalue;

ll cary;

ll sum;

};

segment arr[sz*4];

void changeAB(ll frist_incr,ll last_incr,int node,ll step)

{

arr[node].totalAB += step;

arr[node].first_inc += frist_incr;

arr[node].last_inc += last_incr;

arr[node].sum += ((frist_incr+last_incr)*arr[node].len)/2;

}

void changeC(int node,ll val)

{

arr[node].sum = arr[node].len*val;

arr[node].isSetvalue=1;

arr[node].cary=val;

arr[node].totalAB=0;

arr[node].first_inc=0;

arr[node].last_inc=0;

}

void propagate(int node)

{

ll add1 = arr[node].first_inc;

ll add2 = arr[node].last_inc;

ll step = arr[node].totalAB;

if(arr[node].isSetvalue)

{

ll Left=2*node;

ll Right=2*node+1;

changeC(Left,arr[node].cary);

changeC(Right,arr[node].cary);

arr[node].isSetvalue=0;

arr[node].cary=0;

}

if(add1 || add2 || step)

{

ll Left=2*node;

ll Right=2*node+1;

ll mid=add1+step*(arr[Left].len-1);

changeAB(add1,mid,Left,step);

changeAB(mid+step,add2,Right,step);

arr[node].first_inc=0;

arr[node].last_inc=0;

arr[node].totalAB=0;

}

//update node for the range

void updateAB(int node,int i,int j,ll step)

{

ll Left=arr[node].left,Right=arr[node].right,mid;

ll first_inc,last_inc;

if(i>Right || j<Left)

{

return;

}

if(i<=Left && j>=Right)

{

ll k = step;

if(step>=0)

{

first_inc = (Left-i+1);

last_inc = (Right-i+1);

}

else

{

first_inc = (j-Left+1);

last_inc = (j-Right+1);

}

changeAB(first_inc,last_inc,node,k);

return;

}

else

{

propagate(node);

Left=2*node;

Right=(node<<1) | 1;

updateAB(Left, i, j,step);

updateAB(Right, i, j,step);

arr[node].sum = arr[Left].sum+arr[Right].sum;

return;

}

return;

}

void updateC(int node,int i,int j,ll val)

{

ll Left,Right,mid;

ll b=arr[node].left;

ll e=arr[node].right;

if(i>e || j<b)

return;

else if(i<=b && j>=e)

{

arr[node].sum = (val*(e-b+1));

arr[node].cary=val;

arr[node].isSetvalue=1;

arr[node].totalAB=0;

arr[node].first_inc=0;

arr[node].last_inc=0;

return;

}

else

{

propagate(node);

Left = 2*node;

Right = Left+1;

mid = (b+e)>>1;

updateC(Left,i,j,val);

updateC(Right,i,j,val);

arr[node].sum = (arr[Left].sum+arr[Right].sum);

return;

}

return;

}

ll query(int node,int i,int j)

{

ll b = arr[node].left;

ll e = arr[node].right;

if(i>e || j<b)

{

return 0;

}

if(i<=b && j>=e)

{

return arr[node].sum;

}

propagate(node);

ll Left = node<<1;

ll Right = Left+1;

ll p1 = query(Left, i, j);

ll p2 = query(Right, i, j);

return p1+p2;

}

void _init(int b,int e,int node)

{

arr[node].sum=0; arr[node].len=e-b+1;

arr[node].totalAB=0;

arr[node].cary=0;

arr[node].first_inc=0; arr[node].last_inc=0;

arr[node].isSetvalue=0;

arr[node].left=b;arr[node].right=e;

if(b!=e)

{

int mid=(b+e)/2;

_init(b,mid,node<<1);

_init(mid+1,e,(node<<1)|1);

}

int main()

{

int t;

string s;

int start,end,val;

while(scanf("%d",&t)!=EOF)

{

_init(1,sz-5,1);

while(t--)

{

cin>>s;

if(s[0]=='A')

{

cin>>start>>end;

updateAB(1,start,end,1);//+1 increment increasing ascending order

}

else if(s[0]=='B')

{

cin>>start>>end;

updateAB(1,start,end,-1);//-1 increment decreasing ascending order

}

else if(s[0]=='C')

{

cin>>start>>end>>val;

updateC(1,start,end,val);

}

else if(s[0]=='S')

{

cin>>start>>end;

cout<<query(1,start,end)<<"\n";

}

return 0;

}

Some good links to learn segmented data structure: click here

Category: Segment Tree

11402

12436

Archives

Categories