树状数组、线段树（基础版+懒标记）

单点修改区间查询题目描述一行 NN 个方格开始每个格子里都有一个整数。你需要动态地进行一些操作操作有以下两种类型提问求某一个特定的子区间 [a,b][a,b] 中所有元素的和修改指定某一个格子 xx令 xx 加上或者减去一个特定的值 AA。现在要求你能对每个提问作出正确的回答。输入描述输入文件第一行为一个整数 NN接下来一行包含 nn 个整数表示格子中原来的整数。接下一个正整数 mm再接下来有 mm 行表示 mm 个询问。每个询问的第一个整数表示询问代号询问代号 11 表示增加后面的两个数 xx 和 AA 表示给位置 XX 上的数值增加 AA 询问代号 22 表示区间求和后面两个整数表示 aa 和 bb 表示要求 [a,b][a,b] 之间的区间和。1≤N,X,A≤100000m≤100001≤N,X,A≤100000m≤10000。输出描述共 mm 行每行一个整数表示每个提问的答案。输入输出样例示例输入6 4 5 6 2 1 3 4 1 3 5 2 1 4 1 1 9 2 2 6输出22 22运行限制最大运行时间2s最大运行内存: 512M树状数组实现import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010; static int c[]new int[N];//树状数组 static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { add(i,Integer.parseInt(st.nextToken())); } stnew StringTokenizer(br.readLine()); int mInteger.parseInt(st.nextToken()); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int opeInteger.parseInt(st.nextToken()); if(ope1){ int xInteger.parseInt(st.nextToken()),aInteger.parseInt(st.nextToken()); add(x,a); }else{ int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); bw.write(query(b)-query(a-1)\n); } } br.close(); bw.flush(); bw.close(); } static int lowbit(int x){ return x -x; } static void add(int x,int a){ for (int i x; i n; ilowbit(i)) { c[i]a; } } static int query(int a) { int sum0; for (int i a; i 0; i-lowbit(i)) { sumc[i]; } return sum; } }线段树实现import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010; static int tree[]new int[4*N];//线段树 static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } build(1,1,n); stnew StringTokenizer(br.readLine()); int mInteger.parseInt(st.nextToken()); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int opeInteger.parseInt(st.nextToken()); if(ope1){ int xInteger.parseInt(st.nextToken()),aInteger.parseInt(st.nextToken()); add(1,1,n,x,a); }else{ int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); bw.write(query(1,1,n,a,b)\n); } } br.close(); bw.flush(); bw.close(); } static int query(int id,int l,int r,int x,int y){ if(lx yr){//完全包含 return tree[id]; } int mid(lr)1; int res0; if(xmid)resquery(2*id, l, mid, x, y); if(ymid1)resquery(2*id1, mid1, r, x, y); return res; } static void add(int id,int l,int r,int x,int k){ if(lr){ tree[id]k; return; } int mid(lr)1; if(xmid){ add(2*id, l, mid, x, k); }else{ add(2*id1, mid1, r, x, k); } pushup(id); } static void pushup(int id){ tree[id]tree[2*id]tree[2*id1]; } static void build(int id,int l,int r){ if(lr){ tree[id]a[l]; return; } int mid(lr)1; build(2*id,l,mid); build(2*id1,mid1,r); pushup(id); } }区间修改、区间求和题目描述给定一个长度为 NN 的数组 aa其初值分别为 a1,a2,...,aNa1​,a2​,...,aN​。现有 QQ 个操作操作有以下两种1 l r k将区间 al,al1,...aral​,al1​,...ar​ 的值加上 kk。2 l r求区间 al,al1,...,aral​,al1​,...,ar​ 的和为多少。输入描述输入第 11 行包含两个正整数 N,QN,Q分别表示数组 aa 的长度和操作的个数。第 22 行包含 NN 个非负整数 a1,a2,...,aNa1​,a2​,...,aN​表示数组 aa 元素的初值。第 3∼Q−23∼Q−2 行每行表示一共操作格式为以下两种之一1 l r x2 l r其含义如题所述。1≤N,Q≤1051≤N,Q≤1051≤l≤r≤N1≤l≤r≤N−109≤k,ai≤109−109≤k,ai​≤109。输出描述输出共 QQ 行每行包含一个整数表示相应查询的答案。输入输出样例示例 1输入5 5 1 2 3 4 5 2 1 2 1 2 3 1 2 1 3 1 1 5 1 2 1 5输出3 8 22import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010; static long tree[]new long[4*N];//线段树 static long lazy[]new long[4*N]; static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int qInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } build(1,1,n); for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int opeInteger.parseInt(st.nextToken()); if(ope1){ int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()),kInteger.parseInt(st.nextToken()); add(1,1,n,l,r,k); }else{ int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); bw.write(query(1,1,n,a,b)\n); } } br.close(); bw.flush(); bw.close(); } static long query(int id,int l,int r,int x,int y){ if(lx yr){//完全包含 return tree[id]; } pushdown(id, l, r);//用到才更新 int mid(lr)1; long res0; if(xmid)resquery(2*id, l, mid, x, y); if(ymid1)resquery(2*id1, mid1, r, x, y); return res; } static void add(int id,int l,int r,int x,int y,int k){ if(lx ry){ tree[id](long)k*(r-l1);//注意要乘以区间 //int相乘可能溢出 lazy[id]k;//注意要累加 不要覆盖 return; } pushdown(id,l,r);//用到的时候 现将原来的懒标记的值 先更新好 这时传入lazy[id] int mid(lr)1; if(xmid){ add(2*id, l, mid, x,y,k);//这时传入k } if(ymid1){ add(2*id1, mid1, r, x,y,k); } pushup(id); } static void pushdown(int id,int l,int r){ if(lazy[id]0)return; //只更新下面一层的子节点 int mid(lr)1; tree[2*id]lazy[id]*(mid-l1); //不要覆盖 要累加 lazy[2*id]lazy[id]; tree[2*id1]lazy[id]*(r-(mid1)1); lazy[2*id1]lazy[id]; lazy[id]0;//回传之后置为0 } static void pushup(int id){ tree[id]tree[2*id]tree[2*id1]; } static void build(int id,int l,int r){ if(lr){ tree[id]a[l]; return; } int mid(lr)1; build(2*id,l,mid); build(2*id1,mid1,r); pushup(id); } }