![\"\"](\"https:\/\/cn.hostease.com\/xueyuan\/wp-content\/uploads\/2017\/03\/xian.png\")
<\/a><\/figure>\n\n\n\n<\/p>\n\n\n\n
\u4ece\u56fe\u4e2d\u6211\u4eec\u53ef\u4ee5\u6e05\u695a\u7684\u770b\u5230[0-10]\u88ab\u5212\u5206\u6210\u7ebf\u6bb5\u7684\u5728\u6811\u4e2d\u7684\u5206\u5e03\u60c5\u51b5\uff0c\u9488\u5bf9\u533a\u95f4[0-N]\uff0c\u6700\u591a\u67092N\u4e2a\u8282\u70b9\uff0c\u7531\u4e8e\u662f\u5e73\u8861\u4e8c\u53c9\u6811\u7684\u5f62<\/p>\n\n\n\n
\u5f0f\u4e5f\u53ef\u4ee5\u50cf\u5806\u90a3\u6837\u7528\u6570\u7ec4\u6765\u73a9\uff0c\u4e0d\u8fc7\u66f4\u52a0\u8017\u8d39\u7a7a\u95f4\uff0c\u4e3a\u6700\u591a4N\u4e2a\u8282\u70b9\uff0c\u5728\u9488\u5bf9RMQ\u7684\u95ee\u9898\u4e0a\uff0c\u6211\u4eec\u5e38\u5e38\u5728\u6bcf\u4e2a\u8282\u70b9\u4e0a\u589e\u52a0\u4e00\u4e9bsum\uff0c<\/p>\n\n\n\n
max\uff0cmin\u7b49\u53d8\u91cf\u6765\u8bb0\u5f55\u6c42\u5f97\u7684\u7d2f\u52a0\u503c\uff0c\u5f53\u7136\u4f60\u53ef\u4ee5\u7406\u89e3\u6210\u52a8\u6001\u89c4\u5212\u7684\u601d\u60f3\uff0c\u7531\u4e8e\u62e5\u6709logN\u7684\u65f6\u95f4\uff0c\u6240\u4ee5\u5728RMQ\u95ee\u9898\u4e0a\u6bd4\u6570\u7ec4\u66f4\u52a0\u4f18\u7f8e\u3002<\/p>\n\n\n\n
\u4e8c\uff1a\u4ee3\u7801<\/p>\n\n\n\n
1:\u5728\u8282\u70b9\u4e2d\u5b9a\u4e49\u4e00\u4e9b\u9644\u52a0\u503c\uff0c\u65b9\u4fbf\u6211\u4eec\u5904\u7406RMQ\u95ee\u9898\u3002<\/p>\n\n\n\n
1 #region \u7ebf\u6bb5\u6811\u7684\u8282\u70b9\n 2 \/\/\/ <summary>\n 3 \/\/\/ \u7ebf\u6bb5\u6811\u7684\u8282\u70b9\n 4 \/\/\/ <\/summary>\n 5 public class Node\n 6 {\n 7 \/\/\/ <summary>\n 8 \/\/\/ \u533a\u95f4\u5de6\u7aef\u70b9\n 9 \/\/\/ <\/summary>\n10 public int left;\n11 \n12 \/\/\/ <summary>\n13 \/\/\/ \u533a\u95f4\u53f3\u7aef\u70b9\n14 \/\/\/ <\/summary>\n15 public int right;\n16 \n17 \/\/\/ <summary>\n18 \/\/\/ \u5de6\u5b69\u5b50\n19 \/\/\/ <\/summary>\n20 public Node leftchild;\n21 \n22 \/\/\/ <summary>\n23 \/\/\/ \u53f3\u5b69\u5b50\n24 \/\/\/ <\/summary>\n25 public Node rightchild;\n26 \n27 \/\/\/ <summary>\n28 \/\/\/ \u8282\u70b9\u7684sum\u503c\n29 \/\/\/ <\/summary>\n30 public int Sum;\n31 \n32 \/\/\/ <summary>\n33 \/\/\/ \u8282\u70b9\u7684Min\u503c\n34 \/\/\/ <\/summary>\n35 public int Min;\n36 \n37 \/\/\/ <summary>\n38 \/\/\/ \u8282\u70b9\u7684Max\u503c\n39 \/\/\/ <\/summary>\n40 public int Max;\n41 }\n42 #endregion<\/pre>\n <\/div>\n<\/div>\n\n\n\n2\uff1a\u6784\u5efa(Build)<\/p>\n\n\n\n
\u524d\u9762\u6211\u4e5f\u8bf4\u4e86\uff0c\u6784\u5efa\u6709\u4e24\u79cd\u65b9\u6cd5\uff0c\u6570\u7ec4\u7684\u5f62\u5f0f\u6216\u8005\u94fe\u7684\u5f62\u5f0f\uff0c\u5404\u6709\u7279\u70b9\uff0c\u6211\u5c31\u91c7\u7528\u540e\u8005\uff0c\u65f6\u95f4\u4e3aO(N)\u3002<\/p>\n\n\n\n
\n <\/div>\n 1 #region \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811\"\n 2 \/\/\/ <summary>\n 3 \/\/\/ \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811\"\n 4 \/\/\/ <\/summary>\n 5 \/\/\/ <param name=\"length\"><\/param>\n 6 public Node Build(int[] nums)\n 7 {\n 8 this.nums = nums;\n 9 \n10 return Build(nodeTree, 0, nums.Length - 1);\n11 }\n12 #endregion\n13 \n14 #region \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811\"\n15 \/\/\/ <summary>\n16 \/\/\/ \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811\"\n17 \/\/\/ <\/summary>\n18 \/\/\/ <param name=\"left\"><\/param>\n19 \/\/\/ <param name=\"right\"><\/param>\n20 public Node Build(Node node, int left, int right)\n21 {\n22 \/\/\u8bf4\u660e\u5df2\u7ecf\u5230\u6839\u4e86\uff0c\u5f53\u524d\u5f53\u524d\u8282\u70b9\u7684max\uff0csum\uff0cmin\u503c\uff08\u56de\u6eaf\u65f6\u7edf\u8ba1\u4e0a\u4e00\u5c42\u8282\u70b9\u533a\u95f4\u7684\u503c\uff09\n23 if (left == right)\n24 {\n25 return new Node\n26 {\n27 left = left,\n28 right = right,\n29 Max = nums[left],\n30 Min = nums[left],\n31 Sum = nums[left]\n32 };\n33 }\n34 \n35 if (node == null)\n36 node = new Node();\n37 \n38 node.left = left;\n39 \n40 node.right = right;\n41 \n42 node.leftchild = Build(node.leftchild, left, (left + right) \/ 2);\n43 \n44 node.rightchild = Build(node.rightchild, (left + right) \/ 2 + 1, right);\n45 \n46 \/\/\u7edf\u8ba1\u5de6\u53f3\u5b50\u6811\u7684\u503c(min\uff0cmax\uff0csum)\n47 node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);\n48 node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);\n49 node.Sum = node.leftchild.Sum + node.rightchild.Sum;\n50 \n51 return node;\n52 }\n53 #endregion<\/pre>\n<\/div>\n\n\n\n3\uff1a\u533a\u95f4\u67e5\u8be2<\/p>\n\n\n\n
\u5728\u7ebf\u6bb5\u6811\u4e2d\uff0c\u533a\u95f4\u67e5\u8be2\u8fd8\u662f\u6709\u70b9\u5c0f\u9ebb\u70e6\u7684\uff0c\u5b58\u5728\u4e09\u79cd\u60c5\u51b5\u3002<\/p>\n\n\n\n
\u2460 \u5b8c\u5168\u5305\u542b\uff1a\u4e5f\u5c31\u662f\u8282\u70b9\u7684\u7ebf\u6bb5\u8303\u56f4\u5b8c\u5168\u5728\u67e5\u8be2\u533a\u95f4\u7684\u8303\u56f4\u5185\uff0c\u8fd9\u8bf4\u660e\u6211\u4eec\u8981\u4e48\u5230\u4e86\u201c\u5355\u5143\u8282\u70b9”,\u8981\u4e48\u5230\u4e86\u4e00\u4e2a\u5b50\u533a\u95f4\uff0c\u8fd9\u79cd\u60c5\u51b5<\/p>\n\n\n\n
\u5c31\u662f\u6211\u627e\u5230\u4e86\u67e5\u8be2\u533a\u95f4\u7684\u67d0\u4e00\u4e2a\u5b50\u533a\u95f4\uff0c\u76f4\u63a5\u7d2f\u79ef\u8be5\u533a\u95f4\u503c\u5c31\u53ef\u4ee5\u4e86\u3002<\/p>\n\n\n\n
\u2461 \u5de6\u4ea4\u96c6\uff1a \u8fd9\u79cd\u60c5\u51b5\u6211\u4eec\u9700\u8981\u5230\u5de6\u5b50\u6811\u53bb\u904d\u5386\u3002<\/p>\n\n\n\n
\u2462\u53f3\u4ea4\u96c6\uff1a \u8fd9\u79cd\u60c5\u51b5\u6211\u4eec\u9700\u8981\u5230\u53f3\u5b50\u6811\u53bb\u904d\u5386\u3002<\/p>\n\n\n\n
\u6bd4\u5982\u8bf4\uff1a\u6211\u8981\u67e5\u8be2Sum[4-8]<\/sub>\u7684\u503c,\u6700\u7ec8\u4f1a\u6210\u4e3a:Sum\u603b<\/sub>=Sum[4-4]<\/sub>+Sum[5-5]<\/sub>+Sum[6-8]\uff0c<\/sub>\u65f6\u95f4\u4e3alog(N)\u3002<\/p>\n\n\n\n\n <\/div>\n 1 #region \u533a\u95f4\u67e5\u8be2\n 2 \/\/\/ <summary>\n 3 \/\/\/ \u533a\u95f4\u67e5\u8be2(\u5206\u89e3)\n 4 \/\/\/ <\/summary>\n 5 \/\/\/ <returns><\/returns>\n 6 public int Query(int left, int right)\n 7 {\n 8 int sum = 0;\n 9 \n10 Query(nodeTree, left, right, ref sum);\n11 \n12 return sum;\n13 }\n14 \n15 \/\/\/ <summary>\n16 \/\/\/ \u533a\u95f4\u67e5\u8be2\n17 \/\/\/ <\/summary>\n18 \/\/\/ <param name=\"left\">\u67e5\u8be2\u5de6\u8fb9\u754c<\/param>\n19 \/\/\/ <param name=\"right\">\u67e5\u8be2\u53f3\u8fb9\u754c<\/param>\n20 \/\/\/ <param name=\"node\">\u67e5\u8be2\u7684\u8282\u70b9<\/param>\n21 \/\/\/ <returns><\/returns>\n22 public void Query(Node node, int left, int right, ref int sum)\n23 {\n24 \/\/\u8bf4\u660e\u5f53\u524d\u8282\u70b9\u5b8c\u5168\u5305\u542b\u5728\u67e5\u8be2\u8303\u56f4\u5185\uff0c\u4e24\u70b9\uff1a\u8981\u4e48\u662f\u5355\u5143\u8282\u70b9\uff0c\u8981\u4e48\u662f\u5b50\u533a\u95f4\n25 if (left <= node.left && right >= node.right)\n26 {\n27 \/\/\u83b7\u53d6\u5f53\u524d\u8282\u70b9\u7684sum\u503c\n28 sum += node.Sum;\n29 return;\n30 }\n31 else\n32 {\n33 \/\/\u5982\u679c\u5f53\u524d\u7684left\u548cright \u548cnode\u7684left\u548cright\u65e0\u4ea4\u96c6\uff0c\u6b64\u65f6\u53ef\u8fd4\u56de\n34 if (node.left > right || node.right < left)\n35 return;\n36 \n37 \/\/\u627e\u5230\u4e2d\u95f4\u7ebf\n38 var middle = (node.left + node.right) \/ 2;\n39 \n40 \/\/\u5de6\u5b69\u5b50\u6709\u4ea4\u96c6\n41 if (left <= middle)\n42 {\n43 Query(node.leftchild, left, right, ref sum);\n44 }\n45 \/\/\u53f3\u5b69\u5b50\u6709\u4ea4\u96c6\n46 if (right >= middle)\n47 {\n48 Query(node.rightchild, left, right, ref sum);\n49 }\n50 \n51 }\n52 }\n53 #endregion<\/pre>\n <\/div>\n<\/div>\n\n\n\n4\uff1a\u66f4\u65b0\u64cd\u4f5c<\/p>\n\n\n\n
\u8fd9\u4e2a\u64cd\u4f5c\u8ddf\u6811\u72b6\u6570\u7ec4\u4e2d\u7684\u66f4\u65b0\u64cd\u4f5c\u4e00\u6837\uff0c\u5f53\u9012\u5f52\u7684\u627e\u5230\u5f85\u4fee\u6539\u7684\u8282\u70b9\u540e\uff0c\u6539\u5b8c\u5176\u503c\u7136\u540e\u5728\u5f53\u524d\u8282\u70b9\u4e00\u8def\u56de\u6eaf\uff0c\u5e76\u4e14\u5728\u56de\u6eaf\u7684\u8fc7\u7a0b\u4e2d\u4e00<\/p>\n\n\n\n
\u8def\u4fee\u6539\u7236\u8282\u70b9\u7684\u9644\u52a0\u503c\u76f4\u5230\u6839\u8282\u70b9\uff0c\u81f3\u6b64\u6211\u4eec\u7684\u64cd\u4f5c\u5c31\u5b8c\u6210\u4e86\uff0c\u590d\u6742\u5ea6\u540c\u6837\u4e3alogN\u3002<\/p>\n\n\n\n
\n <\/div>\n 1 #region \u66f4\u65b0\u64cd\u4f5c\n 2 \/\/\/ <summary>\n 3 \/\/\/ \u66f4\u65b0\u64cd\u4f5c\n 4 \/\/\/ <\/summary>\n 5 \/\/\/ <param name=\"index\"><\/param>\n 6 \/\/\/ <param name=\"key\"><\/param>\n 7 public void Update(int index, int key)\n 8 {\n 9 Update(nodeTree, index, key);\n10 }\n11 \n12 \/\/\/ <summary>\n13 \/\/\/ \u66f4\u65b0\u64cd\u4f5c\n14 \/\/\/ <\/summary>\n15 \/\/\/ <param name=\"index\"><\/param>\n16 \/\/\/ <param name=\"key\"><\/param>\n17 public void Update(Node node, int index, int key)\n18 {\n19 if (node == null)\n20 return;\n21 \n22 \/\/\u53d6\u4e2d\u95f4\u503c\n23 var middle = (node.left + node.right) \/ 2;\n24 \n25 \/\/\u904d\u5386\u5de6\u5b50\u6811\n26 if (index >= node.left && index <= middle)\n27 Update(node.leftchild, index, key);\n28 \n29 \/\/\u904d\u5386\u53f3\u5b50\u6811\n30 if (index <= node.right && index >= middle + 1)\n31 Update(node.rightchild, index, key);\n32 \n33 \/\/\u5728\u56de\u6eaf\u7684\u8def\u4e0a\u4e00\u8def\u66f4\u6539\uff0c\u590d\u6742\u5ea6\u4e3algN\n34 if (index >= node.left && index <= node.right)\n35 {\n36 \/\/\u8bf4\u660e\u627e\u5230\u4e86\u8282\u70b9\n37 if (node.left == node.right)\n38 {\n39 nums[index] = key;\n40 \n41 node.Sum = node.Max = node.Min = key;\n42 }\n43 else\n44 {\n45 \/\/\u56de\u6eaf\u65f6\u7edf\u8ba1\u5de6\u53f3\u5b50\u6811\u7684\u503c(min\uff0cmax\uff0csum)\n46 node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);\n47 node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);\n48 node.Sum = node.leftchild.Sum + node.rightchild.Sum;\n49 }\n50 }\n51 }\n52 #endregion<\/pre>\n <\/div>\n<\/div>\n\n\n\n\u6700\u540e\u6211\u4eec\u505a\u4e2a\u4f8b\u5b50\uff0c\u57282000000\u7684\u6570\u7ec4\u7a7a\u95f4\u4e2d\uff0c\u5bfb\u627e200-3000\u533a\u95f4\u6bb5\u7684sum\u503c\uff0c\u770b\u770b\u4ed6\u7684\u8868\u73b0\u5982\u4f55\u3002<\/p>\n\n\n\n
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;<\/span><\/span>namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
int[] nums = new int[200 * 10000];\nfor (int i = 0; i < 10000 * 200; i++)
{
nums[i] = i;
}<\/p>\n
Tree tree = new Tree();<\/p>\n
\/\/\u5c06\u5f53\u524d\u6570\u7ec4\u6784\u5efa\u6210 \u201c\u7ebf\u6bb5\u6811\u201d
tree.Build(nums);<\/p>\n
var watch = Stopwatch.StartNew();<\/p>\n
var sum = tree.Query(200, 3000);<\/p>\n
watch.Stop();<\/p>\n
Console.WriteLine(“\u8017\u8d39\u65f6\u95f4:{0}ms, \u5f53\u524d\u6570\u7ec4\u6709:{1}\u4e2a\u6570\u5b57, \u6c42\u51faSum=:{2}”, watch.ElapsedMilliseconds, nums.Length, sum);<\/p>\n
Console.Read();
}
}<\/p>\n
public class Tree
{
#region \u7ebf\u6bb5\u6811\u7684\u8282\u70b9
\/\/\/ <summary>
\/\/\/ \u7ebf\u6bb5\u6811\u7684\u8282\u70b9
\/\/\/ <\/summary>
public class Node
{
\/\/\/ <summary>
\/\/\/ \u533a\u95f4\u5de6\u7aef\u70b9
\/\/\/ <\/summary>
public int left;<\/p>\n
\/\/\/ <summary>
\/\/\/ \u533a\u95f4\u53f3\u7aef\u70b9
\/\/\/ <\/summary>
public int right;<\/p>\n
\/\/\/ <summary>
\/\/\/ \u5de6\u5b69\u5b50
\/\/\/ <\/summary>
public Node leftchild;<\/p>\n
\/\/\/ <summary>
\/\/\/ \u53f3\u5b69\u5b50
\/\/\/ <\/summary>
public Node rightchild;<\/p>\n
\/\/\/ <summary>
\/\/\/ \u8282\u70b9\u7684sum\u503c
\/\/\/ <\/summary>
public int Sum;<\/p>\n
\/\/\/ <summary>
\/\/\/ \u8282\u70b9\u7684Min\u503c
\/\/\/ <\/summary>
public int Min;<\/p>\n
\/\/\/ <summary>
\/\/\/ \u8282\u70b9\u7684Max\u503c
\/\/\/ <\/summary>
public int Max;
}
#endregion<\/p>\n
Node nodeTree = new Node();<\/p>\n
int[] nums;<\/p>\n
#region \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811”
\/\/\/ <summary>
\/\/\/ \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811”
\/\/\/ <\/summary>
\/\/\/ <param name=”length”><\/param>
public Node Build(int[] nums)
{
this.nums = nums;<\/p>\n
return Build(nodeTree, 0, nums.Length – 1);
}
#endregion<\/p>\n
#region \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811”
\/\/\/ <summary>
\/\/\/ \u6839\u636e\u6570\u7ec4\u6784\u5efa\u201c\u7ebf\u6bb5\u6811”
\/\/\/ <\/summary>
\/\/\/ <param name=”left”><\/param>
\/\/\/ <param name=”right”><\/param>
public Node Build(Node node, int left, int right)
{
\/\/\u8bf4\u660e\u5df2\u7ecf\u5230\u6839\u4e86\uff0c\u5f53\u524d\u5f53\u524d\u8282\u70b9\u7684max\uff0csum\uff0cmin\u503c\uff08\u56de\u6eaf\u65f6\u7edf\u8ba1\u4e0a\u4e00\u5c42\u8282\u70b9\u533a\u95f4\u7684\u503c\uff09
if (left == right)
{
return new Node
{
left = left,
right = right,
Max = nums[left],
Min = nums[left],
Sum = nums[left]
};
}<\/p>\n
if (node == null)
node = new Node();<\/p>\n
node.left = left;<\/p>\n
node.right = right;<\/p>\n
node.leftchild = Build(node.leftchild, left, (left + right) \/ 2);<\/p>\n
node.rightchild = Build(node.rightchild, (left + right) \/ 2 + 1, right);<\/p>\n
\/\/\u7edf\u8ba1\u5de6\u53f3\u5b50\u6811\u7684\u503c(min\uff0cmax\uff0csum)
node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
node.Sum = node.leftchild.Sum + node.rightchild.Sum;<\/p>\n
return node;
}
#endregion<\/p>\n
#region \u533a\u95f4\u67e5\u8be2
\/\/\/ <summary>
\/\/\/ \u533a\u95f4\u67e5\u8be2(\u5206\u89e3)
\/\/\/ <\/summary>
\/\/\/ <returns><\/returns>
public int Query(int left, int right)
{
int sum = 0;<\/p>\n
Query(nodeTree, left, right, ref sum);<\/p>\n
return sum;
}<\/p>\n
\/\/\/ <summary>
\/\/\/ \u533a\u95f4\u67e5\u8be2
\/\/\/ <\/summary>
\/\/\/ <param name=”left”>\u67e5\u8be2\u5de6\u8fb9\u754c<\/param>
\/\/\/ <param name=”right”>\u67e5\u8be2\u53f3\u8fb9\u754c<\/param>
\/\/\/ <param name=”node”>\u67e5\u8be2\u7684\u8282\u70b9<\/param>
\/\/\/ <returns><\/returns>
public void Query(Node node, int left, int right, ref int sum)
{
\/\/\u8bf4\u660e\u5f53\u524d\u8282\u70b9\u5b8c\u5168\u5305\u542b\u5728\u67e5\u8be2\u8303\u56f4\u5185\uff0c\u4e24\u70b9\uff1a\u8981\u4e48\u662f\u5355\u5143\u8282\u70b9\uff0c\u8981\u4e48\u662f\u5b50\u533a\u95f4
if (left <= node.left && right >= node.right)
{
\/\/\u83b7\u53d6\u5f53\u524d\u8282\u70b9\u7684sum\u503c
sum += node.Sum;
return;
}
else
{
\/\/\u5982\u679c\u5f53\u524d\u7684left\u548cright \u548cnode\u7684left\u548cright\u65e0\u4ea4\u96c6\uff0c\u6b64\u65f6\u53ef\u8fd4\u56de
if (node.left > right || node.right < left)
return;<\/p>\n
\/\/\u627e\u5230\u4e2d\u95f4\u7ebf
var middle = (node.left + node.right) \/ 2;<\/p>\n
\/\/\u5de6\u5b69\u5b50\u6709\u4ea4\u96c6
if (left <= middle)
{
Query(node.leftchild, left, right, ref sum);
}
\/\/\u53f3\u5b69\u5b50\u6709\u4ea4\u96c6
if (right >= middle)
{
Query(node.rightchild, left, right, ref sum);
}<\/p>\n
}
}
#endregion<\/p>\n
#region \u66f4\u65b0\u64cd\u4f5c
\/\/\/ <summary>
\/\/\/ \u66f4\u65b0\u64cd\u4f5c
\/\/\/ <\/summary>
\/\/\/ <param name=”index”><\/param>
\/\/\/ <param name=”key”><\/param>
public void Update(int index, int key)
{
Update(nodeTree, index, key);
}<\/p>\n
\/\/\/ <summary>
\/\/\/ \u66f4\u65b0\u64cd\u4f5c
\/\/\/ <\/summary>
\/\/\/ <param name=”index”><\/param>
\/\/\/ <param name=”key”><\/param>
public void Update(Node node, int index, int key)
{
if (node == null)
return;<\/p>\n
\/\/\u53d6\u4e2d\u95f4\u503c
var middle = (node.left + node.right) \/ 2;<\/p>\n
\/\/\u904d\u5386\u5de6\u5b50\u6811
if (index >= node.left && index <= middle)
Update(node.leftchild, index, key);<\/p>\n
\/\/\u904d\u5386\u53f3\u5b50\u6811
if (index <= node.right && index >= middle + 1)
Update(node.rightchild, index, key);<\/p>\n
\/\/\u5728\u56de\u6eaf\u7684\u8def\u4e0a\u4e00\u8def\u66f4\u6539\uff0c\u590d\u6742\u5ea6\u4e3algN
if (index >= node.left && index <= node.right)
{
\/\/\u8bf4\u660e\u627e\u5230\u4e86\u8282\u70b9
if (node.left == node.right)
{
nums[index] = key;<\/p>\n
node.Sum = node.Max = node.Min = key;
}
else
{
\/\/\u56de\u6eaf\u65f6\u7edf\u8ba1\u5de6\u53f3\u5b50\u6811\u7684\u503c(min\uff0cmax\uff0csum)
node.Min = Math.Min(node.leftchild.Min, node.rightchild.Min);
node.Max = Math.Max(node.leftchild.Max, node.rightchild.Max);
node.Sum = node.leftchild.Sum + node.rightchild.Sum;
}
}
}
#endregion
}
}<\/p>\n<\/div>\n\n\n\n![\"\"](\"https:\/\/cn.hostease.com\/xueyuan\/wp-content\/uploads\/2017\/03\/448.png\")
<\/a><\/figure>\n\n\n\n<\/p>\n\n\n\n
\u6587\u7ae0\u6765\u81ea\u7f51\u7edc\u535a\u5ba2https:\/\/www.cnblogs.com\/huangxincheng\/archive\/2012\/12\/08\/2808207.html<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u4e00\u7bc7\u6211\u4eec\u6765\u770b\u6811\u72b6\u6570\u7ec4\u7684\u52a0\u5f3a\u7248\u7ebf\u6bb5\u6811\uff0c\u6811\u72b6\u6570\u7ec4\u80fd\u73a9\u7684\u7ebf\u6bb5\u6811\u4e00\u6837\u53ef\u4ee5\u73a9\uff0c\u800c\u4e14\u80fd\u73a9\u7684\u66f4\u597d\uff0c\u4ed6\u4eec\u5728\u533a\u95f4\u6c42\u548c\uff0c\u6700\u5927\uff0c\u5e73 … \u9605\u8bfb\u66f4\u591a<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[583,584],"class_list":["post-1942","post","type-post","status-publish","format-standard","hentry","category-jishu","tag-583","tag-584"],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack-related-posts":[],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts\/1942","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/comments?post=1942"}],"version-history":[{"count":3,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts\/1942\/revisions"}],"predecessor-version":[{"id":9092,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/posts\/1942\/revisions\/9092"}],"wp:attachment":[{"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/media?parent=1942"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/categories?post=1942"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cn.hostease.com\/xueyuan\/wp-json\/wp\/v2\/tags?post=1942"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}