目录
线段树（具备基本功能：区间查询，区间修改，单点查询，单点修改）
线段树（具备基本功能：区间查询，区间修改，单点查询，单点修改）
#include<pch.h>
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cstring>
#include <cmath>
#define DETERMINATION main
#pragma GCC optimize(2)
#pragma warning(disable:4996)
#define lldin(a) scanf("%lld", &a)
#define println(a) printf("%lld\n", a)
#define print(a) printf("%lld ", a)
#define reset(a, b) memset(a, b, sizeof(a))
#define debug cout<<"procedures above are available"<<endl;
#define BigInteger __int128
using namespace std;
const int INF = 2e9 + 2;
const double PI = acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
//template<typename T>
//inline BigInteger nextBigInteger()
//{
// BigInteger tmp = 0, si = 1;char c; c = getchar();
// while (!isdigit(c))
//{if (c == '-')si = -1;c = getchar();}
// while (isdigit(c))
// {tmp = tmp * 10 + c - '0';c = getchar();}
// return si * tmp;
//}
//std::ostream& operator<<(std::ostream& os, __int128 T)
//{
// if (T<0) os<<"-";if (T>=10 ) os<<T/10;if (T<=-10) os<<(-(T/10));
// return os<<( (int) (T%10) >0 ? (int) (T%10) : -(int) (T%10) ) ;
//}
//void output(BigInteger x)
//{
// if (x < 0)
// {x = -x;putchar('-');}
// if (x > 9) output(x / 10);
// putchar(x % 10 + '0');
// }
/**Maintain your determination.Nobody knows the magnificent landscape
at his destination before the arrival with stumble.**/
/**Last Remote**/
struct node
{
ll left, right, value;
ll laziness;
}nodes[599999];
ll arr[599999];
void construction(ll current,ll left, ll right)
{
nodes[current].left = left, nodes[current].right = right;
if (left == right)
{
nodes[current].value = arr[left];
return ;
}
else
{
ll mid = (left + right) >> 1;
construction(2 * current, left, mid);
construction(2 * current + 1, mid + 1, right);
nodes[current].value = nodes[2 * current].value + nodes[2 * current + 1].value;
}
}
void LazyDown(ll current)
{
nodes[2 * current].laziness+= nodes[current].laziness;
nodes[2 * current + 1].laziness += nodes[current].laziness;
nodes[2 * current].value += (nodes[2 * current].right - nodes[2 * current].left + 1)*nodes[current].laziness;
nodes[2 * current + 1].value += (nodes[2 * current + 1].right - nodes[2 * current + 1].left + 1)*nodes[current].laziness;
nodes[current].laziness = 0;
}
ll investigation(ll current, ll lower, ll upper)
{
if (nodes[current].left >= lower && nodes[current].right <= upper)
{
//cout << nodes[current].value << endl;
return nodes[current].value;
}
else
{
if (nodes[current].laziness > 0)
LazyDown(current);
ll mid = (nodes[current].left +nodes[current].right) >> 1;
ll ans = 0;
if (mid >= lower)
ans += investigation(2 * current, lower, upper);
if (mid < upper)
ans += investigation(2 * current + 1,lower, upper);
nodes[current].value = nodes[2 * current].value + nodes[2 * current + 1].value;
return ans;
}
}
void IntervalModification(ll current, ll lower, ll upper, ll request)
{
if (nodes[current].left >= lower && nodes[current].right <= upper)
{
nodes[current].value += (nodes[current].right - nodes[current].left + 1)*request;
nodes[current].laziness += request;
return ;
}
else
{
if (nodes[current].laziness > 0)
LazyDown(current);
ll mid = (nodes[current].left + nodes[current].right) >> 1;
if (mid >= lower)
IntervalModification(2 * current, lower, upper, request);
if (mid < upper)
IntervalModification(2 * current + 1, lower, upper, request);
nodes[current].value = nodes[2 * current].value + nodes[2 * current + 1].value;
}
}
ll check(ll current, ll tar, ll lower, ll upper)
{
if (nodes[current].left == tar && nodes[current].right == tar)
return nodes[current].value;
else
{
ll mid = (nodes[current].left + nodes[current].right) >> 1;
if (tar <= mid)
return check(2 * current, tar, lower, upper);
else
return check(2 * current + 1, tar, lower,upper);
}
}
int DETERMINATION()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
ll n, m;
cin >> n >> m;
ll sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
/*if(i<=5)
sum += arr[i];*/
}
construction(1,1, n);
//cout << sum << " " << investigation(1, 1, 1) << endl;
//cout << check(1, 1, 1, n) << endl;
for (int i = 1; i <= m; i++)
{
ll com, x, y;
cin >> com >> x >> y;
if (com == 1)
{
ll k;
cin >> k;
IntervalModification(1, x, y, k);
}
else
cout << investigation(1, x, y) << endl;
}
return 0;
}线段树（维护区间最值并查询）
#include<pch.h>
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cstring>
#include <cmath>
#define DETERMINATION main
#pragma GCC optimize(2)
#pragma warning(disable:4996)
#define lldin(a) scanf("%lld", &a)
#define println(a) printf("%lld\n", a)
#define print(a) printf("%lld ", a)
#define reset(a, b) memset(a, b, sizeof(a))
#define debug cout<<"procedures above are available"<<endl;
#define BigInteger __int128
using namespace std;
const int INF = 2e9 + 2;
const double PI = acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
//template<typename T>
//inline BigInteger nextBigInteger()
//{
// BigInteger tmp = 0, si = 1;char c; c = getchar();
// while (!isdigit(c))
//{if (c == '-')si = -1;c = getchar();}
// while (isdigit(c))
// {tmp = tmp * 10 + c - '0';c = getchar();}
// return si * tmp;
//}
//std::ostream& operator<<(std::ostream& os, __int128 T)
//{
// if (T<0) os<<"-";if (T>=10 ) os<<T/10;if (T<=-10) os<<(-(T/10));
// return os<<( (int) (T%10) >0 ? (int) (T%10) : -(int) (T%10) ) ;
//}
//void output(BigInteger x)
//{
// if (x < 0)
// {x = -x;putchar('-');}
// if (x > 9) output(x / 10);
// putchar(x % 10 + '0');
// }
/**Maintain your determination.Nobody knows the magnificent landscape
at his destination before the arrival with stumble.**/
/**Last Remote**/
ll arr[592993];
struct node
{
ll left, right, value;
ll value2;
}nodes[800020];
void cons(ll current, ll left, ll right)
{
nodes[current].left = left, nodes[current].right = right;
if (left == right)
{
nodes[current].value=nodes[current].value2= arr[left];
return;
}
ll mid = (left + right) >> 1;
cons(current << 1, left, mid);
cons(current << 1 | 1, mid + 1, right);
nodes[current].value = max(nodes[current << 1].value, nodes[current << 1 | 1].value);
nodes[current].value2 = min(nodes[current << 1].value2, nodes[current << 1 | 1].value2);
return ;
}
ll mins = INF;
ll query(ll current, ll lower, ll upper)
{
//cout<< nodes[current].left<<" "
if (nodes[current].left >= lower && nodes[current].right <= upper)
{
mins = min(mins, nodes[current].value2);
return nodes[current].value;
}
ll tmp1 = 0, tmp2 = 0;
ll mid = (nodes[current].left+nodes[current].right) >> 1;
if (mid >= lower)
tmp1 = query(current << 1, lower, upper);
if (mid < upper)
tmp2 = query(current << 1 | 1, lower, upper);
return max(tmp1, tmp2);
}
int DETERMINATION()
{
//ios::sync_with_stdio(false);
//cin.tie(0), cout.tie(0);
ll n, q;
lldin(n), lldin(q);
for (int i = 1; i <= n; i++)
lldin(arr[i]);
cons(1, 1, n);
for (int i = 1; i <= q; i++)
{
ll tmp1, tmp2;
lldin(tmp1), lldin(tmp2);
mins = INF;
println(query(1, tmp1, tmp2)-mins);
}
return 0;
}分块算法（具备基本功能）
import java.math.*;
import java.util.*;
import java.io.*;
import java.text.*;
public class Main41
{
static long sum[]= new long[199996];
static long arr[]= new long[199996];
static int blocks[]=new int[199996];
static long lztags[]=new long[199996];
static int blocklength;
public static void setup(long n)
{
blocklength=(int)Math.floor(Math.sqrt((double)n));
//System.out.println(blocklength+"!!");
for(int i=1;i<=n;i++)
{
blocks[i]=(i-1)/blocklength+1;
sum[blocks[i]]+=arr[i];
}
}
public static void IntervalModification(int lower,int upper,long request)
{
for(int i=lower;i<=Math.min(upper,blocks[lower]*blocklength);i++)
{
arr[i]+=request;
sum[blocks[i]]+=request;
}
if(blocks[lower]<blocks[upper])
{
for(int i=(blocks[upper]-1)*blocklength+1;i<=upper;i++)
{
arr[i]+=request;
sum[blocks[i]]+=request;
}
}
for(int i=blocks[lower]+1;i<=blocks[upper]-1;i++)
lztags[i]+=request;
}
public static long IntervalInvestigation(int lower,int upper)
{
long ans=0;
for(int i=lower;i<=Math.min(upper,blocks[lower]*blocklength);i++)
ans+=arr[i]+lztags[blocks[i]];
if(blocks[lower]<blocks[upper])
{
for(int i=(blocks[upper]-1)*blocklength+1;i<=upper;i++)
ans+=arr[i]+lztags[blocks[i]];
}
for(int i=blocks[lower]+1;i<=blocks[upper]-1;i++)
{
ans+=sum[i]+lztags[i]*blocklength;
}
//System.out.println(ans);
return ans;
}
public static void main(String args[])throws IOException
{
StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
st.nextToken();int n=(int)st.nval;
st.nextToken();int m=(int)st.nval;
for(int i=1;i<=n;i++)
{
st.nextToken();
arr[i]=(long)st.nval;
}
setup(n);
for(int i=1;i<=m;i++)
{
int a,b,c,d;
st.nextToken();a=(int)st.nval;
st.nextToken();b=(int)st.nval;
st.nextToken();c=(int)st.nval;
if(a==1)
{
st.nextToken();d=(int)st.nval;
IntervalModification(b,c,d);
}
else if(a==2)
pw.println(IntervalInvestigation(b,c));
}
pw.flush();
pw.close();
}
}树状数组（具备基本功能）
#include<pch.h>
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cstring>
#include <cmath>
#define DETERMINATION main
#pragma GCC optimize(2)
#pragma warning(disable:4996)
#define lldin(a) scanf("%lld", &a)
#define println(a) printf("%lld\n", a)
#define print(a) printf("%lld ", a)
#define reset(a, b) memset(a, b, sizeof(a))
#define debug cout<<"procedures above are available"<<endl;
#define BigInteger __int128
using namespace std;
const int INF = 2e9 + 2;
const double PI = acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
//template<typename T>
//inline BigInteger nextBigInteger()
//{
// BigInteger tmp = 0, si = 1;char c; c = getchar();
// while (!isdigit(c))
//{if (c == '-')si = -1;c = getchar();}
// while (isdigit(c))
// {tmp = tmp * 10 + c - '0';c = getchar();}
// return si * tmp;
//}
//std::ostream& operator<<(std::ostream& os, __int128 T)
//{
// if (T<0) os<<"-";if (T>=10 ) os<<T/10;if (T<=-10) os<<(-(T/10));
// return os<<( (int) (T%10) >0 ? (int) (T%10) : -(int) (T%10) ) ;
//}
//void output(BigInteger x)
//{
// if (x < 0)
// {x = -x;putchar('-');}
// if (x > 9) output(x / 10);
// putchar(x % 10 + '0');
// }
/**Maintain your determination.Nobody knows the magnificent landscape
at his destination before the arrival with stumble.**/
/**Last Remote**/
ll trees[599996];
ll lowbit(ll x)
{
return x & (-x);
}
ll getsum(ll a)
{
ll ans = 0;
while (a > 0)
{
ans += trees[a];
a -= lowbit(a);
}
return ans;
}
void modi(ll loc, ll a,ll limit)
{
while (loc <= limit)
{
trees[loc] += a;
loc += lowbit(loc);
}
}
int DETERMINATION()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
ll n, m;
cin >> n >> m;
reset(trees, 0);
for (int i = 1; i <= n; i++)
{
ll tmp;
cin >> tmp;
modi(i, tmp, n);
}
for (int i = 1; i <= m; i++)
{
ll a, b, c, d;
cin >> a >> b >> c;
if (a == 1)
modi(b, c, n);
else
cout << getsum(c) - getsum(b - 1) << endl;
}
return 0;
}
版权声明：本文为weixin_43874261原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。